Solution: text
class Solution { public: int longestConsecutive(vector& nums) { unordered_set s; for(int i = 0; i < nums.size(); i++){ s.insert(nums[i]); }
int ans = 0;
for(int i = 0; i < nums.size(); i++){
if(s.find(nums[i] - 1) != s.end()){
continue;
}
else {
int count = 0;
int current = nums[i];
while(s.find(current)!=s.end()){
count++;
current++;
}
ans = max(ans, count);
}
}
return ans;
}
};
Leetcode: link
Dry Run
Let's do a dry run on the string "cadbzabcd":
Initial Setup:
str = "cadbzabcd"
set = {} (empty initially) i = 0 j = 0 maxans = 0
-
Iteration 1 (j = 0): Character: 'c' 'c' is not in set, so: Add 'c' to set: set = {'c'} Update maxans = max(0, 0 - 0 + 1) = 1 Move j to 1
-
Iteration 2 (j = 1): Character: 'a' 'a' is not in set, so: Add 'a' to set: set = {'c', 'a'} Update maxans = max(1, 1 - 0 + 1) = 2 Move j to 2
-
Iteration 3 (j = 2): Character: 'd' 'd' is not in set, so: Add 'd' to set: set = {'c', 'a', 'd'} Update maxans = max(2, 2 - 0 + 1) = 3 Move j to 3
-
Iteration 4 (j = 3): Character: 'b' 'b' is not in set, so: Add 'b' to set: set = {'c', 'a', 'd', 'b'} Update maxans = max(3, 3 - 0 + 1) = 4 Move j to 4
-
Iteration 5 (j = 4): Character: 'z' 'z' is not in set, so: Add 'z' to set: set = {'c', 'a', 'd', 'b', 'z'} Update maxans = max(4, 4 - 0 + 1) = 5 Move j to 5
-
Iteration 6 (j = 5): Character: 'a' 'a' is in set (duplicate found), so: Shrink the window by removing the character at i = 0 (which is 'c') from the set: set = {'a', 'd', 'b', 'z'} Move i to 1 (next start index). Still a duplicate: Remove 'a' from the set: set = {'d', 'b', 'z'} Move i to 2 (next start index). No more duplicates, add 'a' to set: set = {'d', 'b', 'z', 'a'}. maxans remains 5. Move j to 6.
-
Iteration 7 (j = 6) Character: 'b' 'b' is in set (duplicate found), so: Shrink the window by removing 'd' from the set: set = {'b', 'z', 'a'} Move i to 3. Still a duplicate: Remove 'b' from the set: set = {'z', 'a'} Move i to 4. No more duplicates, add 'b' to set: set = {'z', 'a', 'b'}. maxans remains 5. Move j to 7.
-
Iteration 8 (j = 7) Character: 'c' 'c' is not in set, so: Add 'c' to set: set = {'z', 'a', 'b', 'c'} Update maxans = max(5, 7 - 4 + 1) = 5 Move j to 8.
-
Iteration 9 (j = 8) Character: 'd' 'd' is not in set, so: Add 'd' to set: set = {'z', 'a', 'b', 'c', 'd'} Update maxans = max(5, 8 - 4 + 1) = 5 j reaches the end of the string.
-
Final Result:
The maximum length of a substring without repeating characters is 5, corresponding to the substring "cadbz".
Let's do a dry run of the code using the array [4, 2, 2, 6, 4] with k = 6.
Initial State:
a = [4, 2, 2, 6, 4]
k = 6
xr = 0 (initial XOR value)
mpp = {0: 1} (map initialized with {0: 1})
cnt = 0 (initial count of subarrays with XOR equal to k)
- Iteration 1 (i = 0, a[0] = 4):
xr = xr ^ a[0] = 0 ^ 4 = 4
x = xr ^ k = 4 ^ 6 = 2
mpp[2] is not in the map, so cnt remains 0.
mpp[xr] = mpp[4]++ => mpp = {0: 1, 4: 1}
- Iteration 2 (i = 1, a[1] = 2):
xr = xr ^ a[1] = 4 ^ 2 = 6
x = xr ^ k = 6 ^ 6 = 0
mpp[0] = 1, so cnt = cnt + mpp[0] = 0 + 1 = 1
mpp[xr] = mpp[6]++ => mpp = {0: 1, 4: 1, 6: 1}
- Iteration 3 (i = 2, a[2] = 2):
xr = xr ^ a[2] = 6 ^ 2 = 4
x = xr ^ k = 4 ^ 6 = 2
mpp[2] is not in the map, so cnt remains 1.
mpp[xr] = mpp[4]++ => mpp = {0: 1, 4: 2, 6: 1}
- Iteration 4 (i = 3, a[3] = 6):
xr = xr ^ a[3] = 4 ^ 6 = 2
x = xr ^ k = 2 ^ 6 = 4
mpp[4] = 2, so cnt = cnt + mpp[4] = 1 + 2 = 3
mpp[xr] = mpp[2]++ => mpp = {0: 1, 4: 2, 6: 1, 2: 1}
- Iteration 5 (i = 4, a[4] = 4):
xr = xr ^ a[4] = 2 ^ 4 = 6
x = xr ^ k = 6 ^ 6 = 0
mpp[0] = 1, so cnt = cnt + mpp[0] = 3 + 1 = 4
mpp[xr] = mpp[6]++ => mpp = {0: 1, 4: 2, 6: 2, 2: 1}
- Final Result: After processing the entire array, the final value of cnt is 4.
Answer: There are 4 subarrays with XOR equal to k = 6.
Subarrays: [4, 2] (XOR = 6) [2, 2, 6] (XOR = 6) [6] (XOR = 6) [4, 2, 2, 6] (XOR = 6)
Thus, the function correctly counts 4 subarrays with an XOR sum of 6.
Initial Setup: Array: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Pointers: left = 0, right = 11 Max Values: left_max = 0, right_max = 0 Trapped Water: water = 0 Step-by-Step Dry Run:
First Move:
Comparison: height[left] (0) < height[right] (1) Action: Since height[left] < height[right], calculate water trapped at left. Water Trapped: left_max - height[left] = 0 - 0 = 0 Update left_max: left_max = max(0, 0) = 0 Move: Increment left to 1.
Second Move:
Comparison: height[left] (1) < height[right] (1) Action: Again, height[left] is less than or equal to height[right], so calculate water trapped at left. Water Trapped: left_max - height[left] = 0 - 1 = 0 Update left_max: left_max = max(0, 1) = 1 Move: Increment left to 2.
Third Move:
Comparison: height[left] (0) < height[right] (1) Action: Calculate water trapped at left. Water Trapped: left_max - height[left] = 1 - 0 = 1 Update left_max: left_max = max(1, 0) = 1 Trapped Water So Far: water = 1 Move: Increment left to 3.
Fourth Move:
Comparison: height[left] (2) > height[right] (1) Action: Since height[left] > height[right], calculate water trapped at right. Water Trapped: right_max - height[right] = 0 - 1 = 0 Update right_max: right_max = max(0, 1) = 1 Move: Decrement right to 10.
Fifth Move:
Comparison: height[left] (2) > height[right] (2) Action: Calculate water trapped at right. Water Trapped: right_max - height[right] = 1 - 2 = 0 Update right_max: right_max = max(1, 2) = 2 Move: Decrement right to 9.
Sixth Move:
Comparison: height[left] (2) > height[right] (1) Action: Calculate water trapped at right. Water Trapped: right_max - height[right] = 2 - 1 = 1 Update right_max: right_max = max(2, 1) = 2 Trapped Water So Far: water = 2 Move: Decrement right to 8.
Seventh Move:
Comparison: height[left] (2) > height[right] (2) Action: Calculate water trapped at right. Water Trapped: right_max - height[right] = 2 - 2 = 0 Update right_max: right_max = max(2, 2) = 2 Move: Decrement right to 7.
Eighth Move:
Comparison: height[left] (2) < height[right] (3) Action: Calculate water trapped at left. Water Trapped: left_max - height[left] = 1 - 2 = 0 Update left_max: left_max = max(1, 2) = 2 Move: Increment left to 4.
Ninth Move:
Comparison: height[left] (1) < height[right] (3) Action: Calculate water trapped at left. Water Trapped: left_max - height[left] = 2 - 1 = 1 Update left_max: left_max = max(2, 1) = 2 Trapped Water So Far: water = 3 Move: Increment left to 5. Tenth Move:
Comparison: height[left] (0) < height[right] (3) Action: Calculate water trapped at left. Water Trapped: left_max - height[left] = 2 - 0 = 2 Update left_max: left_max = max(2, 0) = 2 Trapped Water So Far: water = 5 Move: Increment left to 6. Eleventh Move:
Comparison: height[left] (1) < height[right] (3) Action: Calculate water trapped at left. Water Trapped: left_max - height[left] = 2 - 1 = 1 Update left_max: left_max = max(2, 1) = 2 Trapped Water So Far: water = 6 Move: Increment left to 7. Termination:
Now left = 7 and right = 7, so the loop ends. Final Trapped Water: The total water trapped is 6 units.