Leetcode-Basic/DegreeOfArray.java at main · kavya-7777/Leetcode-Basic · 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
<<<<<<< HEAD
//697. Degree of an Array

class Solution {
    public int findShortestSubArray(int[] nums) {
        int max = 0;
        for(int num : nums){
            max = Math.max(max, num);
        }
        int[] count = new int[max + 1];
        int[] firstIndex = new int[max + 1];
        int[] lastIndex = new int[max + 1];
        for(int i=0;i<firstIndex.length;i++){
            firstIndex[i] = -1;
        }
        for(int i=0;i<nums.length;i++){
            count[nums[i]]++;
            if(firstIndex[nums[i]] == -1) firstIndex[nums[i]] = i;
            lastIndex[nums[i]] = i;
        }
        int degree = 0;
        for(int freq : count){
            degree = Math.max(degree, freq);
        }
        int minLen = Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
            if(count[nums[i]] == degree) minLen = Math.min(minLen, lastIndex[nums[i]] - firstIndex[nums[i]] + 1);
        }
        return minLen;
    }
}

// class Solution {
//     public int findShortestSubArray(int[] nums) {
//         int n = nums.length;
//         HashMap<Integer, int[]> map = new HashMap<>();
//         int degree = 0;
//         for(int i=0;i<n;i++){
//             if(!map.containsKey(nums[i])) map.put(nums[i], new int[]{1, i, i});
//             else{
//                 map.get(nums[i])[0]++;
//                 map.get(nums[i])[2] = i;
//             }
//             degree = Math.max(degree, map.get(nums[i])[0]);
//         }
//         int minLen = nums.length;
//         for(int[] info : map.values()){
//             if(info[0] == degree) minLen = Math.min(minLen, info[2] - info[1] + 1);
//         }
//         return minLen;
//     }
=======
//697. Degree of an Array

class Solution {
    public int findShortestSubArray(int[] nums) {
        int max = 0;
        for(int num : nums){
            max = Math.max(max, num);
        }
        int[] count = new int[max + 1];
        int[] firstIndex = new int[max + 1];
        int[] lastIndex = new int[max + 1];
        for(int i=0;i<firstIndex.length;i++){
            firstIndex[i] = -1;
        }
        for(int i=0;i<nums.length;i++){
            count[nums[i]]++;
            if(firstIndex[nums[i]] == -1) firstIndex[nums[i]] = i;
            lastIndex[nums[i]] = i;
        }
        int degree = 0;
        for(int freq : count){
            degree = Math.max(degree, freq);
        }
        int minLen = Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
            if(count[nums[i]] == degree) minLen = Math.min(minLen, lastIndex[nums[i]] - firstIndex[nums[i]] + 1);
        }
        return minLen;
    }
}

// class Solution {
//     public int findShortestSubArray(int[] nums) {
//         int n = nums.length;
//         HashMap<Integer, int[]> map = new HashMap<>();
//         int degree = 0;
//         for(int i=0;i<n;i++){
//             if(!map.containsKey(nums[i])) map.put(nums[i], new int[]{1, i, i});
//             else{
//                 map.get(nums[i])[0]++;
//                 map.get(nums[i])[2] = i;
//             }
//             degree = Math.max(degree, map.get(nums[i])[0]);
//         }
//         int minLen = nums.length;
//         for(int[] info : map.values()){
//             if(info[0] == degree) minLen = Math.min(minLen, info[2] - info[1] + 1);
//         }
//         return minLen;
//     }
>>>>>>> be6ce0b427078b1421d5dd74adb2300dc02daeec
// }