This is one of those problems where the clean idea matters more than the amount of code. For 697. Degree of an Array, the solution in this repository is mainly a two pointers solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are findShortestSubArray.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.
03
04Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.
05
06Example 1:
07Input: [1, 2, 2, 3, 1]
08Output: 2
09Explanation:
10The input array has a degree of 2 because both elements 1 and 2 appear twice.
11Of the subarrays that have the same degree:
12[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
13The shortest length is 2. So return 2.
14Example 2:
15Input: [1,2,2,3,1,4,2]
16Output: 6
17Note:
18
19nums.length will be between 1 and 50,000.
20nums[i] will be an integer between 0 and 49,999.
21**/
22
23//Runtime: 288 ms, faster than 5.17% of C++ online submissions for Degree of an Array.
24//Memory Usage: 13 MB, less than 92.86% of C++ online submissions for Degree of an Array.
25
26class Solution {
27public:
28 int findShortestSubArray(vector<int>& nums) {
29 map<int, int> count;
30
31 for(int num : nums){
32 if(count.find(num) == count.end()){
33 count[num] = 1;
34 }else{
35 count[num] += 1;
36 }
37 }
38
39 int maxfreq, maxele;
40 vector<int> candidates;
41
42 map<int, int>::iterator it = max_element(count.begin(), count.end(), [] (const pair<int, int> & p1, const pair<int, int> & p2) {return p1.second < p2.second;});
43 maxfreq = it->second;
44
45 for(map<int, int>::iterator it = count.begin(); it!=count.end(); it++){
46 if(it->second == maxfreq){
47 candidates.push_back(it->first);
48 }
49 }
50
51 int ans = INT_MAX;
52 for(int candidate : candidates){
53 vector<int> tofind = {candidate};
54 int substart = find(nums.begin(), nums.end(), candidate) - nums.begin();
55 int subend = find_end(nums.begin(), nums.end(), tofind.begin(), tofind.end()) - nums.begin();
56 cout << maxele << " " << substart << " " << subend << endl;
57 ans = min(ans, subend - substart + 1);
58 }
59 return ans;
60 }
61};
62
63/**
64Approach #1: Left and Right Index [Accepted]
65Intuition and Algorithm
66
67An array that has degree d, must have some element x occur d times. If some subarray has the same degree, then some element x (that occured d times), still occurs d times. The shortest such subarray would be from the first occurrence of x until the last occurrence.
68
69For each element in the given array, let's know left, the index of its first occurrence; and right, the index of its last occurrence. For example, with nums = [1,2,3,2,5] we have left[2] = 1 and right[2] = 3.
70
71Then, for each element x that occurs the maximum number of times, right[x] - left[x] + 1 will be our candidate answer, and we'll take the minimum of those candidates.
72**/
73
74/**
75Complexity Analysis
76
77Time Complexity: O(N)O(N), where NN is the length of nums. Every loop is through O(N)O(N) items with O(1)O(1) work inside the for-block.
78
79Space Complexity: O(N)O(N), the space used by left, right, and count.
80**/
81
82//Runtime: 76 ms, faster than 14.18% of C++ online submissions for Degree of an Array.
83//Memory Usage: 14.4 MB, less than 44.90% of C++ online submissions for Degree of an Array.
84/**
85class Solution {
86public:
87 int findShortestSubArray(vector<int>& nums) {
88 map<int, int> left, right, count;
89 int degree = 0;
90
91 for(int i = 0; i < nums.size(); i++){
92 int x = nums[i];
93 if(left.find(x) == left.end()){
94 left[x] = i;
95 }
96 right[x] = i;
97 if(count.find(x) == count.end()){
98 count[x] = 1;
99 }else{
100 count[x] += 1;
101 }
102 degree = max(degree, count[x]);
103 }
104
105 int ans = nums.size();
106
107 for(map<int, int>::iterator it = count.begin(); it != count.end(); it++){
108 int x = it->first;
109 if(count[x] == degree){
110 ans = min(ans, right[x] - left[x] + 1);
111 }
112 }
113
114 return ans;
115 }
116};
117**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.