DSA/HashingPrbs.java at master · Sriram-sr/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
public class HashingPrbs {
    public static Object[] calculateMaxAndHash(int[] nums) {
        int n = nums.length;
        int max = nums[0];

        for (int idx = 1; idx < n; idx++) {
            if (nums[idx] > max) {
                max = nums[idx];
            }
        }

        int[] hash = new int[max + 1];
        for (int idx = 0; idx < n; idx++) {
            hash[nums[idx]]++;
        }

        return new Object[] { max, hash };
    }

    public static int mostFrequentElement(int[] nums) {
        // Brute O(n + n^2) & O(max)

        // int max = nums[0];
        // for (int idx = 1; idx < nums.length; idx++) {
        // if (nums[idx] > max)
        // max = nums[idx];
        // }

        // int[] visited = new int[max + 1];
        // int maxFreq = -1, maxEle = 0;
        // int count;
        // for (int idx = 0; idx < nums.length; idx++) {
        // if (visited[nums[idx]] != 1) {
        // count = 0;
        // for (int subIdx = 0; subIdx < nums.length; subIdx++) {
        // if (nums[subIdx] == nums[idx]) {
        // count++;
        // }
        // }
        // if (count > maxFreq) {
        // maxEle = nums[idx];
        // maxFreq = count;
        // } else if (count == maxFreq && nums[idx] < maxEle) {
        // maxEle = nums[idx];
        // }
        // visited[nums[idx]] = 1;
        // }
        // }

        // return maxEle;

        // Optimal

        Object[] HashData = HashingPrbs.calculateMaxAndHash(nums);
        int max = (int) HashData[0];
        int[] hash = (int[]) HashData[1];
        int maxFreq = 0, maxEle = -1;
        for (int idx = 0; idx <= max; idx++) {
            if (hash[idx] != 0 && hash[idx] > maxFreq) {
                maxFreq = hash[idx];
                maxEle = idx;
            }
        }

        return maxEle;
    }

    public static int secondMostFrequentElement(int[] nums) {
        Object[] HashData = HashingPrbs.calculateMaxAndHash(nums);
        int max = (int) HashData[0];
        int[] hash = (int[]) HashData[1];

        int ele1Freq = 0, ele2Freq = 0;
        int ele1 = -1, ele2 = -1;

        for (int idx = 0; idx <= max; idx++) {
            if (hash[idx] > ele1Freq) {
                ele2Freq = ele1Freq;
                ele2 = ele1;
                ele1Freq = hash[idx];
                ele1 = idx;
            } else if (hash[idx] < ele1Freq && hash[idx] > ele2Freq) {
                ele2Freq = hash[idx];
                ele2 = idx;
            }
        }

        return ele2;
    }

    public static int sumHighestAndLowestFrequency(int[] nums) {
        Object[] HashData = HashingPrbs.calculateMaxAndHash(nums);
        int max = (int) HashData[0];
        int[] hash = (int[]) HashData[1];

        int maxFreq = hash[0], minFreq = nums.length;
        for (int idx = 0; idx <= max; idx++) {
            if (hash[idx] != 0) {
                if (hash[idx] > maxFreq) {
                    maxFreq = hash[idx];
                }
                if (hash[idx] < minFreq) {
                    minFreq = hash[idx];
                }
            }
        }

        return maxFreq + minFreq;
    }

    public static void main(String[] args) {
        System.out.println(HashingPrbs.mostFrequentElement(new int[] { 2, 4, 3, 2, 5, 4 }));
        System.out.println(
                HashingPrbs.secondMostFrequentElement(new int[] { 10, 9, 7, 7 }));
        System.out.println(HashingPrbs.sumHighestAndLowestFrequency(new int[] { 10, 9, 7, 7, 8, 8, 8 }));
    }
}