DSA Chronicles Day 4: Hashing & Stacks Continued

#programming #cpp #coding #datastructures

Today was a solid day — tackled 4 more problems that deepened my understanding of hashing and stack-based logic. Covered some variety: hash frequency, prefix sum tricks, and even a stack-based temperature-wait problem. Here’s the breakdown:

Problem 1: Search in Sorted Array

Problem:
There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Link to problem: https://leetcode.com/problems/search-in-rotated-sorted-array/description/

Approach:

Used a modified binary search that considers the rotation.
At each step, determine which half of the array is properly sorted.
Based on the sorted half and the target’s value, decide whether to search left or right.
This keeps the time complexity at O(log n).

Topics learned:

Binary Search in rotated arrays
Identifying sorted subarrays within rotated arrays
Time-efficient searching (O(log n))

Problem 2: Daily Temperatures

Problem:
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Link to problem: https://leetcode.com/problems/daily-temperatures/description/

Approach:

Utilized a monotonic stack to keep track of indices of decreasing temperatures.
For each temperature, pop from the stack until a warmer day is found, then calculate the difference in days.

Topics learned:

Monotonic stack pattern
Stack-based array traversal
Efficient future-lookups in O(n) time

Problem 3: Find the Duplicate Number

Problem:
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Link to problem: https://leetcode.com/problems/find-the-duplicate-number/description/

Approach:

Implemented Floyd's Cycle Detection Algorithm (Tortoise and Hare).
Interpreted the array as a linked list where indices are nodes and values are pointers.
The cycle formed by the duplicate is detected.
Later the entry point is the repeated number.

Topics Learned:

Cycle detection in arrays using Floyd’s algorithm
Interpreting array problems as graph traversal

Problem 4: Longest Consecutive Sequence

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:

Used a priority queue (max-heap) to sort the elements in descending order.
Iterated through the queue, popping elements and counting consecutive sequences.
Skipped duplicates. Maintained a running maximum length of consecutive sequences found.

Topics learned: