Chapter•360 Minutes

Items per page

Intermediate DSA Questions — Strings, Arrays, Searching, and Stacks

Core algorithmic problems involving stack evaluations, binary search variations, matrix transformations, two-pointer strategies, and sliding window patterns.

01. Valid Parentheses

Difficulty:EasyPattern:Stack LIFO MatchingTime:O(n)Space:O(n)

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

How It Works & Algorithmic Design

This uses a Stack Data Structure for LIFO (Last-In, First-Out) matching:

Matching Map: Define a map of closing brackets to their corresponding opening brackets (')': '(', '}' : '{', ']': '[').
Stack Operations: Iterate through character ch in string s:
- If ch is an opening bracket ((, {, [), push it onto the stack.
- If ch is a closing bracket, check the stack top. If the stack is empty or stack.pop() does not equal the matching opening bracket, the string is invalid (return false).
Final Check: After processing all characters, return true if stack.length === 0 (all opened brackets were closed).

Why This Approach Works Best

Parentheses nesting follows a LIFO sequence. A stack processes nesting levels naturally in $O(n)$ time complexity and $O(n)$ auxiliary space.

Example Walkthrough

Input: "()[]{}"

Valid balanced string.

Stack Trace: Push '(' -> Pop '(' on ')' | Push '[' -> Pop '[' on ']' | Push '{' -> Pop '{' on '}'

Stack becomes empty at end.

Output: true

Balanced brackets.

Answer: Valid Parentheses using Stack

function isValid(s) {
  const stack = [];
  const map = { ')': '(', '}': '{', ']': '[' };
  for (const ch of s) {
    if (ch in map) {
      if (stack.pop() !== map[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}

💡 Push opening brackets and match closing brackets using LIFO stack evaluation.

Key Takeaways

Stack data structure handles nested structures naturally.
Always check for empty stack conditions before popping.
Runs in $O(n)$ time and $O(n)$ space.

02. Binary Search

Difficulty:EasyPattern:Divide & ConquerTime:O(log n)Space:O(1)

Given a sorted array of integers nums and a target, write a function to search for target in nums in $O(\log n)$ time.

How It Works & Algorithmic Design

Binary Search uses Divide and Conquer on sorted arrays:

Pointers: Set left = 0, right = nums.length - 1.
Mid Calculation: Compute mid = Math.floor((left + right) / 2) (or left + Math.floor((right - left) / 2) to prevent overflow in fixed integer types).
Halving Condition:
- If nums[mid] === target, return mid.
- If nums[mid] < target, discard left half: left = mid + 1.
- If nums[mid] > target, discard right half: right = mid - 1.
Failure: Return -1 if left > right.

Why This Approach Works Best

Halving the search space each iteration reduces search time from linear $O(n)$ to logarithmic $O(\log n)$ time complexity.

Example Walkthrough

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9

Sorted array input.

Step 1: left=0, right=5 -> mid=2 (nums[2]=3). 3 < 9 -> left=3.

Discards left half.

Step 2: left=3, right=5 -> mid=4 (nums[4]=9). Match found!

Target identified at index 4.

Output: 4

Index of target value 9.

Answer: Binary Search implementation

function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

💡 Halves the search range in each iteration using two boundary pointers.

Key Takeaways

Binary search requires the input array to be pre-sorted.
Use left + (right - left) / 2 to avoid integer overflow issues in languages like C++/Java.
Logarithmic time complexity $O(\log n)$ enables ultra-fast searching across large datasets.

03. Best Time to Buy and Sell Stock

Difficulty:EasyPattern:Greedy / Single PassTime:O(n)Space:O(1)

Given an array prices where prices[i] is the stock price on day i, return the maximum profit you can achieve from a single transaction.

How It Works & Algorithmic Design

This uses a Single-Pass Greedy Running Minimum strategy:

Variables: Track minPrice = Infinity and maxProfit = 0.
Iteration: Loop through each stock price in prices:
- If the current price is lower than minPrice, update minPrice = price.
- Otherwise, calculate potential profit: price - minPrice. If this profit exceeds maxProfit, update maxProfit.
Return: Return maxProfit after scanning all prices.

Why This Approach Works Best

Checking every pair of buying/selling days with nested loops takes $O(n^2)$ time. Tracking the lowest price seen so far allows maximum profit calculation in $O(n)$ time and $O(1)$ space.

Example Walkthrough

Input: prices = [7, 1, 5, 3, 6, 4]

Daily stock prices.

Trace: 7 (min=7) -> 1 (min=1) -> 5 (profit=4) -> 3 -> 6 (profit=5, max=5) -> 4

Tracks minPrice and maxProfit concurrently.

Output: 5

Buy on day 2 (price=1), sell on day 5 (price=6).

Answer: Maximum stock profit calculation

function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;
  for (const price of prices) {
    if (price < minPrice) {
      minPrice = price;
    } else if (price - minPrice > maxProfit) {
      maxProfit = price - minPrice;
    }
  }
  return maxProfit;
}

💡 Track the minimum price seen so far and update profit whenever a higher selling price occurs.

Key Takeaways

Stock must be bought before it can be sold (left-to-right order dependency).
Maintain running minimum price to evaluate maximum potential gain.
Single pass achieves $O(n)$ time and $O(1)$ space.

04. Maximum Subarray (Kadane's Algorithm)

Difficulty:MediumPattern:Dynamic Programming / KadaneTime:O(n)Space:O(1)

Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.

How It Works & Algorithmic Design

Solves using Kadane's Dynamic Programming Algorithm:

State Definition: At index $i$, decide whether to add nums[i] to the existing subarray or start a brand new subarray starting at nums[i].
Transition Formula: currentSum = Math.max(nums[i], currentSum + nums[i]).
Global Track: maxSum = Math.max(maxSum, currentSum).
Initialization: Set currentSum = nums[0] and maxSum = nums[0].

Why This Approach Works Best

Brute force checking all contiguous subarrays takes $O(n^2)$ time. Kadane's algorithm makes local optimal decisions at every step, reducing the runtime to optimal linear $O(n)$ time and $O(1)$ auxiliary space.

Example Walkthrough

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Array containing negative and positive integers.

Kadane Trace: Subarray [4, -1, 2, 1] gives currentSum=6, which is the highest recorded.

Restarts subarray when current sum drops below current element.

Output: 6

Maximum contiguous subarray sum.

Answer: Kadane's Algorithm implementation

function maxSubArray(nums) {
  let currentSum = nums[0];
  let maxSum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

💡 Iterative dynamic programming approach to find maximum contiguous subarray sum.

Key Takeaways

Decides whether to extend current subarray or start fresh at each index.
Works correctly even if all numbers in the array are negative.
Optimal linear runtime of $O(n)$ time and $O(1)$ space.

05. Container With Most Water

Difficulty:MediumPattern:Two Pointers ShrinkingTime:O(n)Space:O(1)

Given an integer array height of length $n$, find two lines that together with the x-axis form a container that holds the most water.

How It Works & Algorithmic Design

Solves using Two Pointers Shrinking Boundary:

Pointers: Position left = 0 and right = height.length - 1.
Area Calculation: width = right - left. Area = Math.min(height[left], height[right]) * width.
Max Update: maxWater = Math.max(maxWater, area).
Pointer Movement Strategy: To potentially find a taller boundary that compensates for reduced width, move the pointer that points to the shorter height (if (height[left] < height[right]) left++ else right--).

Why This Approach Works Best

Evaluating all pairs of lines takes $O(n^2)$ time. Moving the shorter pointer guarantees that higher potential areas are checked while eliminating inferior choices in $O(n)$ time and $O(1)$ space.

Example Walkthrough

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

Heights of vertical lines.

Optimal Pair: Index 1 (height 8) and Index 8 (height 7)

Width = 8 - 1 = 7. Area = min(8, 7) * 7 = 49.

Output: 49

Maximum area of water contained.

Answer: Container with most water using two pointers

function maxArea(height) {
  let left = 0, right = height.length - 1;
  let maxWater = 0;
  while (left < right) {
    const h = Math.min(height[left], height[right]);
    const w = right - left;
    maxWater = Math.max(maxWater, h * w);
    if (height[left] < height[right]) left++;
    else right--;
  }
  return maxWater;
}

💡 Calculate area and always move the pointer pointing to the shorter vertical line.

Key Takeaways

Always move the pointer corresponding to the shorter boundary line.
Width continuously decreases, so height must increase to improve area.
Runs in linear $O(n)$ time and $O(1)$ space.

06. Longest Substring Without Repeating Characters

Difficulty:MediumPattern:Sliding WindowTime:O(n)Space:O(k)

Given a string s, find the length of the longest substring without repeating characters.

How It Works & Algorithmic Design

Solves using the Variable Sliding Window with Hash Map Indexing:

Pointers: Maintain a sliding window defined by left boundary left and right boundary right.
Map Index Tracking: Use a Hash Map charIndexMap to store the last seen index of each character.
Expansion & Contraction: Expand right across string s:
- If character s[right] was seen inside the current window (charIndexMap[s[right]] >= left), update left = charIndexMap[s[right]] + 1 to skip past the repeating character.
- Update charIndexMap[s[right]] = right.
- Calculate window size (right - left + 1) and update maxLength.

Why This Approach Works Best

Instead of resetting the window or using nested loops ($O(n^2)$), jumping left directly past previous duplicate positions ensures each character is processed efficiently in $O(n)$ time and $O(k)$ space.

Example Walkthrough

Input: s = "abcabcbb"

Target string.

Window Execution: "abc" (len=3) -> 'a' repeats at idx 3 -> move left to idx 1 ("bca") -> len=3

Sliding window dynamically adjusts left edge.

Output: 3

Longest unique substring is "abc".

Answer: Sliding window unique substring search

function lengthOfLongestSubstring(s) {
  const map = new Map();
  let left = 0, maxLength = 0;
  for (let right = 0; right < s.length; right++) {
    if (map.has(s[right]) && map.get(s[right]) >= left) {
      left = map.get(s[right]) + 1;
    }
    map.set(s[right], right);
    maxLength = Math.max(maxLength, right - left + 1);
  }
  return maxLength;
}

💡 Dynamically adjust window boundary using character index mapping.

Key Takeaways

Store character indices to jump left pointer instantly.
Ensure the recorded index is $\ge left$ to avoid moving backwards.
Linear time complexity $O(n)$ with $O(k)$ space for distinct characters.

07. Merge Intervals

Difficulty:MediumPattern:Sorting / SweepingTime:O(n log n)Space:O(n)

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals.

How It Works & Algorithmic Design

Solves using Interval Sorting and Sequential Merging:

Sort: Sort intervals based on their start times (interval[0]). This brings overlapping candidate intervals next to each other.
Iterate & Merge:
- Initialize merged = [intervals[0]].
- For each subsequent interval:
  - Get lastMerged = merged[merged.length - 1].
  - If interval.start <= lastMerged.end, an overlap exists. Merge by updating lastMerged.end = Math.max(lastMerged.end, interval.end).
  - Otherwise, no overlap; push interval into merged.
Return: Return merged.

Why This Approach Works Best

Sorting takes $O(n \log n)$ time. Once sorted, a single $O(n)$ linear scan processes all merges cleanly.

Example Walkthrough

Input: [[1,3],[2,6],[8,10],[15,18]]

List of unmerged interval pairs.

Merge Step: [1,3] and [2,6] overlap (2 <= 3) -> Merge to [1,6]. [8,10] and [15,18] do not overlap.

Combines overlapping ranges.

Output: [[1,6],[8,10],[15,18]]

Final merged interval list.

Answer: Merge overlapping intervals

function merge(intervals) {
  if (intervals.length <= 1) return intervals;
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const curr = intervals[i];
    if (curr[0] <= last[1]) {
      last[1] = Math.max(last[1], curr[1]);
    } else {
      result.push(curr);
    }
  }
  return result;
}

💡 Sort intervals by start time and merge overlapping end boundaries sequentially.

Key Takeaways

Sorting by start time ensures overlapping candidates are adjacent.
Use Math.max on end points to handle fully enclosed sub-intervals.
Time complexity is dominated by sorting: $O(n \log n)$.

08. Rotate Image (2D Matrix)

Difficulty:MediumPattern:Matrix ManipulationTime:O(n^2)Space:O(1)

Given an $n \times n$ 2D matrix representing an image, rotate the image by 90 degrees clockwise in-place.

How It Works & Algorithmic Design

Mathematical transformation through Transpose then Reverse:

Step 1: Transpose Matrix (Swap rows and columns across main diagonal):
- For every $i$ from $0$ to $n-1$ and $j$ from $i+1$ to $n-1$, swap matrix[i][j] with matrix[j][i].
Step 2: Reverse Each Row:
- For each row $i$, reverse elements horizontally (left and right pointers swapping matrix[i][left] and matrix[i][right]).

Why This Approach Works Best

Transpose + Reverse turns $90^\circ$ rotation into two clean, in-place matrix ops. Avoids $O(n^2)$ extra memory allocation, achieving true $O(1)$ space and $O(n^2)$ time complexity.

Example Walkthrough

Input: [[1,2,3],[4,5,6],[7,8,9]]

3x3 matrix.

After Transpose: [[1,4,7],[2,5,8],[3,6,9]]

Rows converted to columns.

After Row Reversal: [[7,4,1],[8,5,2],[9,6,3]]

Each row reversed horizontally.

Output: [[7,4,1],[8,5,2],[9,6,3]]

Rotated 90 degrees clockwise.

Answer: In-place 90-degree matrix rotation

function rotate(matrix) {
  const n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  for (let i = 0; i < n; i++) {
    matrix[i].reverse();
  }
}

💡 Transpose matrix across diagonal, then reverse each row horizontally.

Key Takeaways

Rotate clockwise = Transpose matrix + Reverse rows.
Rotate counter-clockwise = Transpose matrix + Reverse columns.
Performs in-place updates achieving $O(1)$ extra space and $O(n^2)$ time.

09. Group Anagrams

Difficulty:MediumPattern:Hash Map BucketingTime:O(n * k log k)Space:O(n * k)

Given an array of strings strs, group the anagrams together in any order.

How It Works & Algorithmic Design

Solves using Hash Map Grouping with Canonical Key Signature:

Key Signature: Two strings are anagrams if and only if their sorted character representations are identical (e.g., "eat" $\to$ "aet" and "tea" $\to$ "aet").
Map Setup: Maintain a Hash Map where key = sortedStringKey and value = array of original strings.
Grouping: Loop through each string s in strs:
- Compute sortedKey = s.split('').sort().join('').
- Append s to map[sortedKey].
Return: Return Object.values(map).

Why This Approach Works Best

Sorted string keys group all anagram variants into matching buckets in $O(n \cdot k \log k)$ time, where $n$ is string count and $k$ is max string length.

Example Walkthrough

Input: ["eat","tea","tan","ate","nat","bat"]

List of unsorted strings.

Key Groups: "aet": ["eat","tea","ate"] | "ant": ["tan","nat"] | "abt": ["bat"]

Grouped by canonical sorted string key.

Output: [["eat","tea","ate"],["tan","nat"],["bat"]]

Bucketed list of anagram groups.

Answer: Group anagrams using sorted key map

function groupAnagrams(strs) {
  const map = {};
  for (const s of strs) {
    const key = s.split('').sort().join('');
    if (!map[key]) map[key] = [];
    map[key].push(s);
  }
  return Object.values(map);
}

💡 Use sorted characters as map keys to group anagram words together.

Key Takeaways

Canonical representation (like sorted character strings) unifies identical frequency structures.
Character count tuples ($26$-length arrays) can optimize key creation to $O(k)$ per word.
Space complexity is $O(n \cdot k)$ to store string references.

10. Product of Array Except Self

Difficulty:MediumPattern:Prefix/Suffix AccumulationTime:O(n)Space:O(1)

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i], without using division in $O(n)$ time.

How It Works & Algorithmic Design

Solves using Prefix and Suffix Product Accumulation:

Left Products Pass: Create result array res. Set res[0] = 1. For $i$ from $1$ to $n-1$, compute res[i] = res[i - 1] * nums[i - 1] (stores product of all elements to the left of $i$).
Right Products Pass: Maintain running right = 1. Loop backwards from $n-1$ down to $0$:
- res[i] = res[i] * right.
- Update right = right * nums[i].
Return: res contains total prefix $\times$ suffix products for every index.

Why This Approach Works Best

Avoids division by zero crashes and achieves linear $O(n)$ time using $O(1)$ extra memory (excluding output array).

Example Walkthrough

Input: nums = [1, 2, 3, 4]

Target input.

Left Pass: res = [1, 1, 2, 6]

Products of elements to the left.

Right Pass: res = [24, 12, 8, 6]

Multiplied by suffix running products.

Output: [24, 12, 8, 6]

Products except self.

Answer: Product of array except self

function productExceptSelf(nums) {
  const n = nums.length;
  const res = new Array(n);
  res[0] = 1;
  for (let i = 1; i < n; i++) {
    res[i] = res[i - 1] * nums[i - 1];
  }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    res[i] *= right;
    right *= nums[i];
  }
  return res;
}

💡 Combine left prefix products and right suffix products in two simple passes.

Key Takeaways

Combines prefix product and suffix product without using division.
Reuses output array space to achieve true $O(1)$ auxiliary memory.
Linear time complexity $O(n)$.

01. Valid Parentheses

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Valid Parentheses using Stack

02. Binary Search

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Binary Search implementation

03. Best Time to Buy and Sell Stock

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Maximum stock profit calculation

04. Maximum Subarray (Kadane's Algorithm)

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Kadane's Algorithm implementation

05. Container With Most Water

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Container with most water using two pointers

06. Longest Substring Without Repeating Characters

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Sliding window unique substring search

07. Merge Intervals

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Merge overlapping intervals

08. Rotate Image (2D Matrix)

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: In-place 90-degree matrix rotation

09. Group Anagrams

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Group anagrams using sorted key map

10. Product of Array Except Self

How It Works & Algorithmic Design

Why This Approach Works Best

Answer: Product of array except self

STAY UPDATED WITH BYTES!