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

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.

May 16, 2025 - 12:02

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

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.