DEV Community: Amruta

DSA Chronicles Day 4: Hashing & Stacks Continued

Amruta — Mon, 19 May 2025 18:00:05 +0000

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:

Identifying consecutive sequences in a sorted context
Understanding time complexity trade-offs (O(n log n) vs O(n))

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

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

Amruta — Sat, 17 May 2025 15:09:46 +0000

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:

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

Final Approach:

Used Sliding Window technique with two pointers start and end.
Maintained a count array to track how many times a character appeared in the current window.
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.
Calculated current window size.

What I Learned:

Sliding Window is a powerful technique to maintain a valid subarray or substring within two moving pointers.
You must shrink the window properly using a loop to remove duplicate characters until the substring becomes valid.
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:

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

Final Approach:

Sort all intervals based on their starting times using a lambda function.
Initialize a new list to hold merged intervals.
Traverse the sorted intervals.
If the merged list is empty or there is no overlap, simply add the interval.
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:

How to use a lambda function in C++ to sort a 2D vector based on specific criteria (start time here).
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:

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

Final Approach:

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

What I Learned:

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.
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:

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

What I Learned:

Prefix sum helps reduce nested loops by tracking accumulated values.
Hash maps enable quick lookups for previous prefix sums — making the algorithm linear time.
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:

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

What I Learned:

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

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

DSA Chronicles Day 2: 5 More Problems, 5 Core Logics

Amruta — Fri, 16 May 2025 10:33:15 +0000

I'm back with another set of 5 DSA problems I tackled today! Today, I’ve focused on explaining both my first approach and final solution. Along with this I have also mentioned what each technique actually enables you to do. Hopefully, this helps anyone who's also in the middle of building their intuition.

Problem 1: Group Anagrams

Problem:
Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Link to problem: https://leetcode.com/problems/group-anagrams/description/

Approach:

First Thought:

Tried comparing all strings against each other for anagram checks. I t was too slow.

Final Approach:

Sort each string alphabetically and use it as a key in a hash map.
Group all original strings under the same sorted key.

Topics I learned:

Hash maps allow grouping items based on custom logic (like sorted strings).
Sorting gives a unique "signature" to each anagram group.

Problem 2: Kth Largest Element in Array

Problem:
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.

Link to problem: https://leetcode.com/problems/kth-largest-element-in-an-array/description/

Approach:

First Thought:

Sorted the whole array and picked the (n-k)th largest — wasteful.

Final Approach:

Used a min-heap (priority queue) of size k.
Pushed elements while maintaining only the k largest; top of the heap is the answer.

Topics I learned:

Heaps are great for finding the top/bottom k elements in O(n log k) time.
Min-heaps automatically remove the smallest element when full — perfect for this case.
Use priority queues when you need constant-time access to the current best/worst element.

Problem 3: Valid Parentheses

Problem:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Link to problem: https://leetcode.com/problems/valid-parentheses/description/

Approach:

First Thought:

Tried overly complicated edge checks before thinking about a stack.
Manually compared character positions instead of thinking in terms of a data structure.

Final Approach:

Used a stack to push opening brackets.
For closing brackets, checked the top of the stack for a valid match and popped it.

Topics I learned:

Stacks are ideal for problems with nested structures or LIFO (last-in-first-out) logic.
Helps easily manage matching pairs (e.g., open/close).
Stacks are good for dealing with balancing or backtracking logic.

Problem 4: Longest Repeating Character Replacement

Problem:
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Link to problem: https://leetcode.com/problems/longest-repeating-character-replacement/description/

Approach:

First Thought:

Used nested loops to check every possible substring — too slow for large inputs.

Final Approach:

Used a sliding window to track the longest substring that can be made valid by replacing ≤ k characters.
Maintained a character frequency map and window size.

Topics I learned:

Sliding Window is great for efficiently processing substrings in linear time. In particular when problem asks for "longest/shortest substring with constraint".
When coupled with a frequency map, it helps avoid redundant calculations and keep state within the window.

Problem 5: Rotate Array

Problem:
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Link to problem: https://leetcode.com/problems/rotate-array/description/

Approach:

First Thought:

Shifted each element manually in a loop — messy and O(n²).

Final Approach:

Used the reverse technique:
Reverse the full array
Reverse the first k elements
Reverse the rest

Topics I learned:

Array reversal tricks are clean and efficient (O(n) time, O(1) space).
Understanding in-place algorithms improves space efficiency without using extra data structures.

My code link: https://github.com/Amruta-25/dsa_chronicles.git

Can’t wait to continue this journey on Day 3.

ML-chronicles: Day 1 Understanding KNN with Iris Dataset

Amruta — Thu, 15 May 2025 18:10:02 +0000

Understanding KNN with Iris Dataset – A Beginner's Visual Guide

Introduction
As part of my ml-chronicles series, I decided to start things off with a foundational yet powerful algorithm: K-Nearest Neighbors (KNN).
Before diving in, I skimmed through some great GFG articles to grasp the theory. Later I followed a YouTube tutorial to understand how it’s applied practically. I wanted this project to be more interactive. So, I added several features to visualize the model's behavior.And also explored its evaluation metrics interactively.
This post covers follwing stuff:

Building a KNN model from scratch,
Applying it to the Iris dataset,
Visualizing the results,
Testing with custom inputs, and
Optimizing the best value of k.

Credits and resources:
GFG article: https://www.geeksforgeeks.org/k-nearest-neighbours/
Youtube tutorial: https://youtu.be/mpfU9n4MzBE?feature=shared

What is KNN ?

KNN stands for K-Nearest Neighbors. It is also called as lazy learning algorithm. It doesn’t train a model explicitly. It doesn't learn from the training set immediately but stores the dataset and at the time of classification performs action on the dataset. It looks at the k nearest data points around a query and returns the most common class among them.
If dataset has significant outliers or noise a higher k helps smooth out predictions and noise.. However very high k can often cause underfitting.
There are various statistical methods for selecting best value of k : cross-validation, elbow method, odd values for k etc.
Also the distances can be measured in some of the famous methods: Euclidean distance, Manhattan distance, Minkowski distance etc.
Steps involved:
1.Measure distance (usually Euclidean) to all training points.
2.Pick the k closest ones.
3.Vote on the class label.
KNN works best with normalized data and small to medium datasets.

The Dataset: IRIS
The classic Iris dataset has:

150 samples across 3 classes: Setosa, Versicolor, and Virginica.
4 numerical features: Sepal Length, Sepal Width, Petal Length, and Petal Width.
For my project: I removed the Id column and normalized all features using MinMaxScaler. Further I Mapped class labels to numeric codes (1, 2, 3) for internal processing.

My Model Architecture
Preprocessing

Normalized all feature columns to [0, 1].
Mapped species to numeric values for classification.
Used 3D scatter plots to visualize separability among classes.

Custom KNN from Scratch
I implemented KNN in a separate module (kNN_modules.py).
It includes:

A distance function to measure closeness: formula for euclidean distance is used.
A KNN() function that predicts the class using statistics.mode() from nearest neighbors.
Optional print to view selected neighbors. This helped me build intuition about how predictions are formed.

Visualizations: Following visuals were implemented .. I am attaching the results

Confusion Matrix
Used sklearn’s ConfusionMatrixDisplay to evaluate predictions visually for a fixed k=5.

Accuracy Heatmap
I ran 10 random train-test splits (30% test) and varied k from 1 to 15.
Then visualized accuracy trends across combinations using a heatmap.

Best k – Average Accuracy Plot
I Computed average accuracy for each k value across runs.
Thus found the best_k using .idxmax().

Export
Saved all accuracy results to CSV for later inspection.

Interactive Query Input
One of my favorite parts was enabling this command-line prediction:
User can input 4 features like: SepalL SepalW PetalL PetalW
Input is scaled and classified using the custom KNN function
It prints the predicted species!

(It might skip in non-interactive environments — I handled that too.)

Results & Observations
The model performed best at k = 9, with average accuracy peaking there.
Visualization helped reveal class boundaries and overlaps

Writing the KNN logic from scratch gave me a hands-on view of its behavior.

Features I Added

Normalization using MinMaxScaler
Confusion Matrix using sklearn
Heatmap of accuracy vs. k
Interactive command-line query support
CSV export for tracking experimental results

My code link: https://github.com/Amruta-25/ML_chronicles_KNN.git

This was Day 1 of my ml-chronicles.
If you're just starting out in ML — try building this from scratch.
What would you add or change in this project?

DSA Chronicles Day 1 : 5 Essential Problems I Solved

Amruta — Thu, 15 May 2025 07:43:54 +0000

Today was a productive day in my DSA journey! I tackled five important problems, each teaching me something new about logic, data structures, and implementation. Some problems I cracked independently, and others with some help — but all were solid learning experiences. Here's a breakdown of what I solved and what I learned:

Problem 1: Top K Frequent Elements in Array

Problem:
Given a non-empty integer array arr[] of size n, find the top k elements which appear most frequently. If two numbers have the same frequency, prefer the larger one.

Link to problem: https://www.geeksforgeeks.org/problems/top-k-frequent-elements-in-array/1

Approach:

Use an unordered_map to count the frequency of each number.
Push the entries into a priority_queue (max-heap) that prioritizes higher frequency (and higher value in case of ties).
Extract the top k elements from the heap.

Topics I learned:

Unordered map: Helped me count frequencies in linear time—essential for frequency-based problems.
Priority queue (max-heap): Learned how to structure a custom comparator and use a heap to get the most frequent or largest values efficiently.

Problem 2: Reduce Array Size to Half

Problem:
Given an array arr, remove as few elements as possible (completely) so that the size of the remaining array is at most half the original.

Link to problem: https://leetcode.com/problems/reduce-array-size-to-the-half/description/

Approach:

Count element frequencies using a hashmap.
Use a max-heap to remove the most frequent elements first.
Keep removing until the remaining elements are ≤ half the array size.

Topics I learned:

Greedy selection with heaps: Understood that removing elements with the highest frequency first ensures minimal removal steps.
Hashmap + heap pattern: Reinforced how this duo helps in optimizing decisions based on frequency.

Problem 3: Remove K Digits

Problem:
Given a number as a string num and an integer k, remove k digits to form the smallest possible number.

Link to problem : https://leetcode.com/problems/remove-k-digits/

Approach:

Traverse left to right, greedily remove digits where the left digit is larger than the right.
If k is still > 0, remove from the end.
Finally, trim leading zeros.

Topics I learned:

Greedy stack-based approach: Learned how removing bigger digits early helps form a smaller number.
String and digit manipulation: Got familiar with trimming zeros and using stack-like behavior on strings.

Problem 4: Longest Substring with Distinct Characters

Problem:
Given a string s, return the length of the longest substring with all unique characters.

Link to problem: https://www.geeksforgeeks.org/problems/longest-distinct-characters-in-string5848/1

Approach:

Use a sliding window and an ASCII array to track last-seen indices of characters.
Shift the window forward whenever a repeating character is found inside the current window.

Topics I learned:

Sliding window technique: Understood how to dynamically maintain a substring using two pointers and optimize space.
Character-index tracking: Practiced using arrays to map ASCII values for fast lookups.

Problem 5: Sum of Digits of String After Convert

Problem:
Given a lowercase string s and an integer k, convert each character to its alphabet position, sum the digits, and repeat k times.

Link to problem: https://leetcode.com/problems/sum-of-digits-of-string-after-convert/description/

Approach:

Convert characters to numbers using 'char' - 'a' + 1 rule.
Sum digits repeatedly k times.

Topics I learned:

ASCII to int conversion: Learned how to map characters like 'a' to 1 using basic arithmetic.
Digit transformation: Practiced repeatedly converting and summing numbers using string manipulation.

My code link: https://github.com/Amruta-25/dsa_chronicles.git