This is one of those problems where the clean idea matters more than the amount of code. For 594. Longest Harmonious Subsequence, the solution in this repository is mainly a greedy solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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: greedy.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are findLHS.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- 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(2^n). Number of subsequences generated will be 2^n.
- Space: O(1)O(1). Constant space required.
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 152 ms, faster than 21.92% of C++ online submissions for Longest Harmonious Subsequence.
02//Memory Usage: 22.4 MB, less than 28.30% of C++ online submissions for Longest Harmonious Subsequence.
03
04/**
05Approach 3: Using Sorting
06**/
07
08/**
09Complexity Analysis
10Time complexity : O(nlogn). Sorting takes O(nlogn) time.
11Space complexity : O(logn). logn space is required by sorting in average case.
12**/
13
14class Solution {
15public:
16 int findLHS(vector<int>& nums) {
17 map<int, int> count;
18 vector<int> key;
19
20 int ans = 0;
21
22 sort(nums.begin(), nums.end());
23
24 for(int n : nums){
25 if(count.find(n) == count.end()){
26 count[n] = 1;
27 key.push_back(n);
28 }else{
29 count[n]++;
30 }
31 }
32
33 for(int i = 1; i < key.size(); i++){
34 int k1 = key[i], k2 = key[i-1];
35 if(k1 - k2 == 1) ans = max(ans, count[k1] + count[k2]);
36 // cout << k1 << ", " << k2 << ", " << count[k1] << ", " << count[k2] << endl;
37 }
38
39 return ans;
40 }
41};
42
43/**
44Approach 1: Brute Force
45generate all possible subsequences, and then check if they are harmonic
46**/
47/**
48Complexity Analysis
49Time complexity : O(2^n). Number of subsequences generated will be 2^n.
50Space complexity : O(1)O(1). Constant space required.
51**/
52
53//TLE
54
55/**
56class Solution {
57public:
58 int findLHS(vector<int>& nums) {
59 int ans = 0;
60 //1<<nums.size(): pow(2, nums.size())
61 for(int i = 0; i < 1<<nums.size(); i++){
62 int count = 0;
63 int curmin = INT_MAX, curmax = INT_MIN;
64 for(int j = 0; j < nums.size(); j++){
65 //i&(1<<j): the jth digit of binary representation of i
66 if((i&(1<<j)) != 0){
67 curmin = min(curmin, nums[j]);
68 curmax = max(curmax, nums[j]);
69 count++;
70 }
71 }
72 if((int)((long long)curmax-(long long)curmin) == 1) ans = max(ans, count);
73 }
74 return ans;
75 }
76};
77**/
78
79/**
80Approach 2: Better Brute Force
81based on an element, find elements form harmonic sequence with it
82**/
83/**
84Complexity Analysis
85Time complexity : O(n^2). Two nested loops are there.
86Space complexity : O(1). Constant space required.
87**/
88//TLE
89
90/**
91class Solution {
92public:
93 int findLHS(vector<int>& nums) {
94 int ans = 0;
95 for(int i = 0; i < nums.size(); i++){
96 int count = 0;
97 bool isHarmonic = false;
98 for(int j = 0; j < nums.size(); j++){
99 if(nums[j] == nums[i]){
100 count++;
101 }else if(nums[j] + 1 == nums[i]){
102 count++;
103 isHarmonic = true;
104 }
105 }
106 if(isHarmonic) ans = max(ans, count);
107 }
108 return ans;
109 }
110};
111**/
112
113/**
114Approach 4: Using HashMap
115build map and then find continuous key
116**/
117
118/**
119Complexity Analysis
120Time complexity : O(n). One loop is required to fill mapmap and one for traversing the mapmap.
121Space complexity : O(n). In worst case map size grows upto size nn.
122**/
123
124/**
125class Solution {
126public:
127 int findLHS(vector<int>& nums) {
128 map<int, int> count;
129 int ans = 0;
130 for(int n : nums){
131 if(count.find(n) == count.end()){
132 count[n] = 1;
133 }else{
134 count[n]++;
135 }
136 }
137
138 for(map<int, int>::iterator it = count.begin(); it != count.end(); it++){
139 int k = it->first;
140 if(count.find(k+1) != count.end()){
141 ans = max(ans, count[k]+count[k+1]);
142 }
143 }
144
145 return ans;
146 }
147};
148**/
149
150/**
151Approach 5: In Single Loop
152build map and check for harmonic subsequences at the same time
153**/
154
155/**
156Complexity Analysis
157Time complexity : O(n). Only one loop is there.
158Space complexity : O(n). mapmap size grows upto size n.
159**/
160
161//Runtime: 212 ms, faster than 6.62% of C++ online submissions for Longest Harmonious Subsequence.
162//Memory Usage: 20.7 MB, less than 84.91% of C++ online submissions for Longest Harmonious Subsequence.
163
164/**
165class Solution {
166public:
167 int findLHS(vector<int>& nums) {
168 map<int, int> count;
169 int ans = 0;
170 for(int n : nums){
171 if(count.find(n) == count.end()){
172 count[n] = 1;
173 }else{
174 count[n]++;
175 }
176 if(count.find(n+1) != count.end()){
177 ans = max(ans, count[n]+count[n+1]);
178 }
179 if(count.find(n-1) != count.end()){
180 ans = max(ans, count[n]+count[n-1]);
181 }
182 }
183 return ans;
184 }
185};
186**/Cost
Complexity
Time
O(2^n). Number of subsequences generated will be 2^n.
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(1)O(1). Constant space required.
Auxiliary state plus the answer structure where the problem requires one.