DSA Chronicles Day 3: Solidifying the Core – 5 Problems, 5 Learnings

Problem 1 Longest Substring Without Repeating Characters

Problem:
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Link to problem: https://leetcode.com/problems/longest-consecutive-sequence/description/

Approach:

First Thought:

1. Used a basic count[256] array to track frequency of characters.
2. Tried checking frequency and updating start directly if a duplicate was found.
3. Misplaced order of start++ and count[s[start]]–, which caused logic errors for overlapping characters.

Final Approach:

1. Used Sliding Window technique with two pointers start and end.
2. Maintained a count array to track how many times a character appeared in the current window.
3. On detecting a duplicate character (count[s[end]] > 1), shrunk the window using a while loop. Then decreased count[s[start]] and moved start forward.
4. Calculated current window size.

What I Learned:

1. Sliding Window is a powerful technique to maintain a valid subarray or substring within two moving pointers.
2. You must shrink the window properly using a loop to remove duplicate characters until the substring becomes valid.
3. Frequency map or array helps in quickly checking if a character is repeating inside the window.
   This approach avoids unnecessary recomputation and gives O(n) time complexity.

Problem 2 Merge Intervals

Problem:
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Link to problem: https://leetcode.com/problems/merge-intervals/description/

Approach:

First Thought:

1. Comparing ending times first and merging based on that.
2. Considered checking if the current interval starts before the previous one ends and adjusting the range accordingly.
3. Realized that sorting by start times is essential to group potential overlapping intervals effectively.

Final Approach:

1. Sort all intervals based on their starting times using a lambda function.
2. Initialize a new list to hold merged intervals.
3. Traverse the sorted intervals.
4. If the merged list is empty or there is no overlap, simply add the interval.
5. If the current interval overlaps with the last merged interval, update the end of the last merged interval to the maximum of both ends.

What I Learned:

1. How to use a lambda function in C++ to sort a 2D vector based on specific criteria (start time here).
2. The importance of sorting before greedy merging

Problem 3 Top K Frequent Elements

Problem:
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Link to problem: https://leetcode.com/problems/top-k-frequent-elements/description/

Approach:

First Thought:

1. I knew I had to count frequencies but wasn’t clear on how to extract top k efficiently.
2. Thought of sorting the full hash map, but it’s inefficient (O(n log n)).
3. Forgot to actually create the (frequency, number) pair before pushing into the heap.

Final Approach:

1. Build a hash_map where the key is the number and the value is its frequency.
2. Create a max heap with the frequency as the first element so that the most frequent elements come first.
3. Traverse the map, push each (frequency, number) pair into the heap.
4. Pop the top k elements from the heap and store the numbers in a result vector.

What I Learned:

1. Realized that (frequency, element) should be the order in the pair if I want to sort based on frequency using the default max-heap behavior.
2. Understood how a heap helps simulate the behavior of a dynamic “Top K” structure—automatically. They maintain the most relevant (frequent) elements at the top.

Problem 4 Subarray Sum Equal K

Problem:
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Link to problem: https://leetcode.com/problems/subarray-sum-equals-k/description/

Approach:

1. Maintained a running prefix sum while traversing the array.
2. Used a hash map to store frequency of each prefix sum encountered.
3. At each step, checked if (prefixSum – k) exists in the map — indicating a subarray that sums to k.
4. Initialized the map with {0: 1} to account for subarrays starting at index 0.

What I Learned:

1. Prefix sum helps reduce nested loops by tracking accumulated values.
2. Hash maps enable quick lookups for previous prefix sums — making the algorithm linear time.
3. This technique is a common pattern in problems that involve subarrays with given sum.

Problem 5 3Sum

Problem:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Link to problem: https://leetcode.com/problems/3sum/description/

Approach:

1. Used prefix sum to keep track of cumulative sums while traversing the array.
2. Maintained a hash map to store frequency of each prefix sum.
3. For every index, I checked if a subarray ending there has a sum of k using: prefix_sum – k
4. If yes, I increased the count by how many times this difference has appeared before.
5. Initialized the hash map with {0: 1} to handle edge cases when subarray starts at index 0.

What I Learned:

1. Prefix sums are powerful tools for subarray problems.
2. Hash maps can efficiently track previous prefix sums to find subarrays in O(n) time.
3. This approach improves over brute-force which is O(n²).

Link to my code: https://github.com/Amruta-25/dsa_chronicles.git