DSA

Problem Overview We are given the head of a singly linked list. We need to reverse the linked list. Follow-up: Solve it iteratively and recursively. Leetcode - Linked List Cycle Example Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Key Observations In a singly linked list, we can only traverse forward. Each node contains a pointer to the next node. Reversing the list means changing the direction of every next pointer. We must carefully store the next node before modifying links. Approach 1: Brute Force (Using Stack) Intuition Traverse the list. Push every node onto a stack. Pop nodes one by one to rebuild the list in reverse order. Code class Solution { public: ListNode* reverseList(ListNode* head) { if (!head) return NULL; stack<ListNode*> st; ListNode* curr = head; while (curr != NULL) { st.push(curr); curr = curr->next; } ListNode* newHead = st.top(); st.pop(); curr = newHead; while (!st.empty()) { curr->next = st.top(); st.pop(); curr = curr->next; } curr->next = NULL; return newHead; } }; Why It Is Not Optimal Uses extra data structure (stack). Requires additional memory. The problem can be solved in-place. Time and Space Complexity Time: O(n) Space: O(n) Approach 2: Three Pointer (Optimal Iterative) Intuition We maintain three pointers: ...

Problem Overview We are given a 2D array of characters named board. The board size is m x n. We are also given a string word. Our goal is to find whether the word exists in the board. If found → return true, otherwise → return false. LeetCode - Word Search Example Input: board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "ABCCED" Output: true ...

Problem Overview We are given a 2D matrix of size n * n. The matrix represents an image. Our goal is to rotate the image by 90 degrees clockwise. The solution must use constant extra space (in-place). LeetCode - Rotate Image Example Input: matrix = [[1,2,3], [4,5,6], [7,8,9]] Output: [[7,4,1], [8,5,2], [9,6,3]] Intuition If we remember basic matrix properties: Transpose of a matrix Reverse of each row If we: First take the transpose (swap (i,j) with (j,i)) Then reverse every row We effectively rotate the matrix 90° clockwise. ...

Problem Overview We are given a matrix of size m * n. We need to return all elements of the matrix in spiral order. Note: The matrix is not necessarily square. LeetCode - Spiral Matrix Example Input: matrix = [[1,2,3], [4,5,6], [7,8,9]] Output: [1,2,3,6,9,8,7,4,5] Intuition We need to travese the matrix in this order Indices traversal: (0,0) → (0,1) → (0,2) right (0,2) ↓ (1,2) ↓ (2,2) down (2,2) ← (2,1) ← (2,0) left (2,0) ↑ (1,0) up (1,0) → (1,1) right So the movement pattern becomes: ...

Problem Overview We are given a matrix of size m * n. If any element in the matrix is 0, set its entire row and column to 0. Constraint: The solution must use O(1) extra space. LeetCode - Set Matrix Zeroes Example Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]] Brute Force Intuition and Approach Use an unordered_map to store positions of original zeros. In a second traversal: ...

Problem Overview We are given an array heights of size n. The value at each index represents the height of a vertical bar. We need to find two bars such that together they can hold the maximum amount of water. Note: We are not allowed to slant the container. LeetCode - Container With Most Water Example Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 ...

Problem Overview We are given an integer array nums, We need to find all unique triplets [nums[i], nums[j], nums[k]] such that: i != j, i != k, j != k nums[i] + nums[j] + nums[k] == 0 We need to return unique triplets Notice that the order of the output and the order of the triplets does not matter. LeetCode - Three Sum Example Input: [-1, 0, 1, 2, -1, -4] Output: [[-1,-1,2], [-1,0,1]] Explanation: ...

Problem Overview We are given a sorted array nums of distinct integers The array has been possibly rotated at some pivot k (unknown). Example: Original: [0,1,2,4,5,6,7] Rotated : [4,5,6,7,0,1,2] We must return the index of target if it exists in the array else return -1. The required time complexity is O(log n). LeetCode - Search in Rotated Sorted Array Brute Force Approach The simplest approach is to scan the entire array. ...

Problem Overview We are given an array nums The array was originally sorted in ascending order and then left-rotated by k positions, where 1 < k < n All elements in the array are unique We need to find the minimum element in the array The goal is to design a solution with O(log n) time complexity How I Approached the Problem I follow a strict rule when solving problems like this: ...

Overview You’re given a list of stock prices where each index represents a day. You are allowed only one transaction: Buy on one day Sell on a future day Your goal is simple: maximize profit. If no profit is possible, return 0. Problem Constraints 1 <= prices.length <= 10^5 Expected time complexity: O(n) Only one buy and one sell Sell must happen after buy How I Approached the Problem I follow a strict rule when solving problems like this: ...