Skip to content
Tutorials Center
My learning

Topics

Lesson 220 of 225 ยท Practice and Review

Practice Problems: Arrays, Strings and Hashing

Twelve graded problems on arrays, strings and hash maps, from Two Sum to trapping rain water. Each has a hint, a brute force, the fast solution and tests.

Reading about a technique is not the same as using it. This lesson gives you twelve problems on arrays, strings and hashing, ordered from warm-up to hard. Every problem follows the same routine you should use in an interview: understand the question, write the brute force, find the idea that removes the extra work, then check edge cases.

For each problem we give the statement, a hint (read it only if you are stuck), and then a full runnable solution with tests. The best way to use this page: read the statement, close your eyes on the solution, try it in the editor of your choice, and only then compare. Where it is practical, the solution is checked against a slow brute-force version on random inputs, so you can see that the clever version is also correct.

Before coding any problem, answer four questions: What are the inputs and their limits? What does the output look like for an empty or one-element input? What is the brute force and its cost? Which pattern from the cheat sheet removes the repeated work?

Problem 1: Two Sum (easy)

Given a list of integers nums and a target, return the indexes [i, j] with i < j of two numbers that add up to target, or None if there is no such pair. Assume at most one answer matters (return the first found).

Hint. For each number you need its complement, target - number. How can you find out in O(1) whether you have already seen it?

The brute force tries every pair in O(n^2). Remembering each number's index in a dictionary turns the search into one pass:

Python Solution 1: Two Sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(n). We check before inserting so an element is never paired with itself, and [3, 3] still works because the first 3 is stored before the second is examined.

Problem 2: Group Anagrams (easy)

Given a list of words, group the words that are anagrams of each other (same letters, any order). Keep groups in order of first appearance.

Hint. Two words are anagrams exactly when their sorted letters are equal. A tuple or string of sorted letters can be a dictionary key.

Python Solution 2: group anagrams

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n * L log L) for n words of length L (sorting each word); space O(n * L). For very long words you can use a 26-slot letter count as the key instead, making it O(n * L).

Problem 3: Best Time to Buy and Sell (easy)

prices[i] is a stock price on day i. Choose one day to buy and a later day to sell. Return the maximum profit, or 0 if no profit is possible.

Hint. If you sell today, the best buy day is the cheapest day so far. Track it while scanning.

Python Solution 3: single pass

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(1). This is a tiny example of keeping a running summary (the minimum so far) instead of re-scanning the past.

Problem 4: Remove Duplicates from a Sorted Array (easy)

Given a sorted list, remove duplicates in place so each value appears once, and return the new length k. The first k entries must hold the unique values in order. Do not allocate another list.

Hint. Use two pointers: a read pointer that scans everything, and a write pointer marking the end of the unique prefix.

Python Solution 4: two pointers in place

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(1). See two pointers and partitioning for more in-place tricks.

Problem 5: Valid Parentheses (easy)

Given a string containing only ()[]{}, decide whether it is balanced: every opener is closed by the same kind of bracket, in the correct order.

Hint. The most recent opener must be the first to close. That is last-in, first-out.

Python Solution 5: a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(n). Two bugs to avoid: popping from an empty stack, and forgetting to check that the stack is empty at the end. More in stack applications.

Problem 6: Product of Array Except Self (medium)

Return a list where result[i] is the product of all elements except nums[i]. Do not use division, and aim for O(n) time.

Hint. result[i] = (product of everything left of i) * (product of everything right of i). Build the left products in one pass, then multiply in the right products in a second pass.

Python Solution 6: prefix and suffix products

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), extra space O(1) beyond the output. Zeros are handled for free because we never divide.

Problem 7: Longest Consecutive Sequence (medium)

Given an unsorted list of integers, return the length of the longest run of consecutive values (like 3, 4, 5, 6), in O(n) time. Order in the input does not matter.

Hint. Sorting costs O(n log n). Put everything in a set and only start counting from numbers that have no predecessor (x - 1 is absent).

Python Solution 7: a set and run starts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n) even though there is a nested loop: each number is visited by the inner while only when it is part of a run that started at a run-start, so every number is counted once overall. Space O(n).

Problem 8: Rotate an Array (medium)

Rotate a list to the right by k steps in place with O(1) extra space. For [1,2,3,4,5,6,7] and k = 3 the result is [5,6,7,1,2,3,4].

Hint. Reverse the whole list, then reverse the first k elements and the remaining n - k elements separately. Do not forget k %= n.

Python Solution 8: three reversals

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(1). Why it works: reversing everything puts the last k elements first but backwards; reversing each block restores their order.

Problem 9: Merge Intervals (medium)

Given a list of [start, end] intervals, merge all overlapping ones and return the result sorted by start. Intervals that touch ([1,4] and [4,5]) count as overlapping.

Hint. After sorting by start, an interval either extends the last merged interval or begins a new one.

Python Solution 9: sort and sweep

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n log n) for the sort, space O(n). The max matters: a later interval may be fully inside the previous one ([1,10] then [2,3]). More on this in interval scheduling.

Problem 10: Longest Substring with At Most K Distinct Characters (medium)

Given a string s and an integer k, return the length of the longest substring that contains at most k different characters.

Hint. Slide a window. Keep a count of each character in it. When the window has more than k distinct characters, move the left edge forward until it is valid again.

Python Solution 10: sliding window

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n): both left and right only move forward. Space O(k). See sliding window.

Problem 11: Minimum Window Substring (hard)

Given strings s and t, return the shortest substring of s that contains every character of t (including duplicates), or "" if none exists. If several windows tie, return the leftmost.

Hint. Count what t needs. Expand the right edge until all needs are met, then shrink the left edge as far as possible while staying valid, recording the best window each time. Track how many requirements are still unmet instead of re-checking all counts.

Python Solution 11: expand and shrink

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n + m) for |s| = n, |t| = m: each pointer moves forward at most n times. Space O(m) for the counter (plus any extra distinct characters seen).

Problem 12: Trapping Rain Water (hard)

height[i] is the height of a wall of width 1. After rain, how many units of water are trapped between the walls? For [0,1,0,2,1,0,1,3,2,1,2,1] the answer is 6.

Hint. The water above position i is min(tallest wall to the left, tallest wall to the right) - height[i]. Computing both maxima for every i is O(n^2). Can two pointers moving inward, tracking the left and right maxima, replace that? Always move the side with the lower wall: its water level is decided by that wall.

Python Solution 12: two pointers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(1). The correctness argument: when height[left] < height[right], the right side already has a wall at least as tall as height[left], so the water at left is limited only by left_max.

What to practise next

  • Re-solve from scratch a few days later, without looking. If you cannot, the idea has not stuck yet.
  • Change the constraints. What if the array is sorted? What if memory is limited? What if the data arrives as a stream?
  • Write the brute force first every time; it is your test oracle.
  • Continue with Practice Problems: Trees, Graphs and DP.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the Two Sum solution insert a number into the dictionary after checking for its complement?

    Checking first means only earlier elements are candidates, so an element cannot match itself, yet two equal values at different positions still pair up.
  2. 2. In Longest Consecutive Sequence, why is the algorithm O(n) despite the nested while loop?

    Only run starts enter the inner loop, and every number belongs to exactly one run, so the total number of inner steps is at most n.
  3. 3. What is the key idea behind rotating a list in place with three reversals?

    A full reversal moves the last k items to the front in reverse order, and reversing the two blocks separately puts each block back in its original order.
  4. 4. Which statement about the sliding-window solution for at most K distinct characters is true?

    The left pointer advances inside the while loop but never goes back, so together both pointers move at most 2n steps.
  5. 5. Which tool turns "find the matching complement" from O(n) per element into O(1)?

    A dictionary or set tests membership in O(1) on average, so each complement lookup no longer scans the list.

Summary

  • Twelve problems, one routine: state the brute force, find the repeated work, remove it with a pattern, test the edges.
  • Hash maps and sets: Two Sum, Group Anagrams, Longest Consecutive Sequence.
  • Running summaries: Best Time to Buy and Sell, Product Except Self (prefix and suffix).
  • Two pointers: Remove Duplicates, Rotate (reversals), Trapping Rain Water.
  • Windows and counters: At Most K Distinct, Minimum Window.
  • Stack and sorting: Valid Parentheses; Merge Intervals (sort, then sweep).
  • Checking a fast solution against a brute force on random small inputs is the quickest way to find bugs.

Next: Practice Problems: Trees, Graphs and DP