Arrays, Strings & Hashing

These are the warm-ups that open a Google coding round and the spans-and-matching problems that turn into the hard one. They run from a one-minute hash map to a Hard that stacks three ideas on top of each other. None of them are exotic. Google grades whether you reach the right structure on instinct. You then explain why it works while you type into a Google Doc that will not run your code.

Three structures cover this group. A hash map or set answers "have I seen this key" in constant time, which kills nested-loop scans. A stack matches things that nest, like brackets, and remembers what is still open. A monotonic stack or deque stays sorted as you push. In a single pass it answers "what is the next greater element" or "how wide a span can this value command." Learn those three. The rest is bookkeeping.

How Google frames it

Google does not hand you the textbook title. It buries the problem inside a business scenario and trusts you to recognize the shape underneath. Two Sum arrives as "match each ad request to the one budget line that fills it." Valid Parentheses becomes "validate that these nested config blocks open and close correctly." Same algorithm. The business framing is there to slow you down. Cut past the scenario to the structure fast, then name it and reason about edge cases before you write a line. That speed is what they're watching for.

Nothing in the Doc runs. You win the round out loud instead. Write the solution, then walk one short input through it by hand and name the invariant, the rule your structure never breaks: "the stack always holds exactly the brackets still waiting to close." A candidate who only memorized a template can't produce that line. One who understands the structure says it without thinking. And it's the only proof of correctness anyone in the room gets.

The Google angle

Googleyness and communication get scored in the same hour as your code, not parked in a separate behavioral round. On these problems that shows up as edge-case discipline: empty input, a single element, an all-same array, brackets that close before anything opens. The Doc won't run, so naming those cases yourself is the only proof you handle them. Name them before you type. And treat a hint as a collaboration to lean into, not a slip to paper over.

The three structures to know

Nearly everything in this group is one of these three, or a small mix of them.

Pattern 1: Hash map or set for O(1) lookup

A hash map (Python's dict) stores key-to-value pairs and looks any key up in roughly O(1) time; a hash set does the same for bare membership. You walk the array once and, at each element, ask the structure a question it answers instantly: have I seen the complement I need? Is this value's neighbor present? You write into the structure as you go, so each element both queries and updates it.

def two_sum(nums, target):
    seen = {}                          # value -> index, filled as we go
    for i, n in enumerate(nums):
        need = target - n              # the partner that completes the pair
        if need in seen:               # O(1) lookup: have we passed it already?
            return [seen[need], i]
        seen[n] = i                    # remember this value for a later element
    return []

The brute force checks every pair, which is O(n²). The map collapses that to O(n) by remembering each value the instant you pass it, so the partner check is one lookup instead of a rescan. The same instinct powers the consecutive-sequence problem below, where a hash set turns an O(n log n) sort into a clean O(n) sweep.

Pattern 2: Stack for matching what nests

A stack is last-in, first-out: you push items on and pop the most recent one off. That ordering is exactly what nesting needs. When you read an opener you push it; when you read a closer the thing it must match is whatever you pushed most recently, sitting right on top. The stack always holds precisely the items still waiting to be closed, in the order they were opened.

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}   # closer -> its opener
    stack = []
    for ch in s:
        if ch in pairs:                # a closer: top of stack must be its opener
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)           # an opener: remember it until its closer arrives
    return not stack                   # any leftover openers -> unbalanced

The invariant carries the proof. At every step the stack holds exactly the unmatched openers seen so far. A closer that finds the wrong opener on top, or an empty stack, means the string was never balanced. State that sentence and the correctness argument is finished.

Pattern 3: Monotonic stack for next greater and widest span

A monotonic stack keeps its contents sorted (here, by height) as you push. Before pushing a new bar you pop every bar that is taller than or equal to it. That incoming shorter bar is the wall that finally stops each of them from extending right. The moment a bar pops, you know both edges of the widest rectangle it can anchor, so you compute its area on the spot. Each bar is pushed once and popped once, so the sweep runs O(n) overall.

def largest_rectangle_area(heights):
    stack = []                         # (start_index, height), heights increasing bottom->top
    best = 0
    for i, h in enumerate(heights + [0]):   # trailing 0 forces the stack to flush at the end
        start = i
        while stack and stack[-1][1] >= h:  # this shorter bar stops every taller bar to its left
            idx, height = stack.pop()
            best = max(best, height * (i - idx))   # width runs from idx up to here
            start = idx                # the new bar can extend left to where that taller bar began
        stack.append((start, h))
    return best

This histogram routine is the engine behind Maximal Rectangle below, the highest-frequency hard problem in this group. The same "pop until the new value breaks the order" mechanic, on a deque instead of a stack, gives the sliding-window maximum at the end. The Foundations stack lesson drills the base mechanics; here we go straight to the spins Google puts on it.

The Google angle

Google ladders its follow-ups: a medium opens the round, then the interviewer twists it into a harder variant to see how far your structure bends. Two Sum becomes "return all pairs, with duplicates" or "the pair closest to the target." Valid Parentheses becomes "what is the minimum number of insertions to make it valid." Google does not repeat the exact public question, so memorizing the answer is useless; what transfers is the pattern. Solve the opener cleanly and fast, and you bank the minutes the twist will need.

Asked at Google

Four problems, hardest structure last. Two Sum is the hash-map warm-up and Longest Consecutive Sequence is the hash-set trick. Valid Parentheses is the canonical stack, and Maximal Rectangle stacks the monotonic histogram on top of a row sweep. Read each spec twice. Say your edge cases before you type.

The Google angle

Almost none of these arrive with their textbook name attached. Two Sum shows up as matching requests to budgets, Valid Parentheses as checking that nested config opens and closes. The base algorithm is assumed. What Google watches is how you adapt it live and keep talking while you do. So when the spec buries the pattern in product language, say it back in plain terms, name the structure you'll lean on, and walk one input by hand before a line of code. That hand-walk is the only read the Doc gives the interviewer.

1

Two Sum: One-Pass Hash Map

EasyCommonly asked

Problem

Given an integer array nums and an integer target, return the indices of the two numbers that add up to target. Exactly one valid pair exists, and you may not use the same element twice. Return the indices in any order.

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

nums[0] + nums[1] = 2 + 7 = 9.

Input: nums = [3,2,4], target = 6

Output: [1,2]

nums[1] + nums[2] = 2 + 4 = 6; the two 3s would reuse one index.

How this uses the pattern

For each number, the partner you need is target minus it. Keep a hash map from value to index, and check for that partner before you store the current number.

Two Sum: One-Pass Hash Map

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [2,7,11,15], 9Expected: [0, 1]

Input: [3,2,4], 6Expected: [1, 2]

Input: [3,3], 6Expected: [0, 1]

Need a hint? (3 available)

The Google angle

This is the warm-up that opens a Google loop, and the test is whether you reach for the hash map on instinct rather than nesting two loops. Google rarely asks it by name; it arrives as "match each ad request to the budget line that exactly fills it." The follow-up ladder is where the round really goes: return all pairs, or the pair whose sum is closest to the target. Name the one-pass map and why it is O(n), because the Doc cannot run it to compare against the brute force.

Take it further

What if you must return every pair that sums to the target, with duplicate values allowed? A single value-to-index map no longer suffices, because a value can appear many times. Switch to a map from value to a list of indices, or sort the array and walk two pointers inward, collecting pairs and skipping over equal values so you do not emit the same pair twice.

Show solution & walkthrough

2

Longest Consecutive Sequence: Hash Set Run-Starts

MediumCommonly asked

Problem

Given an unsorted array of integers nums, return the length of the longest run of consecutive integers (for example 1, 2, 3, 4) that can be formed from its values. The elements do not need to be adjacent in the array. Solve it in O(n) time.

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

Output: 4

The run 1, 2, 3, 4 has length 4. 100 and 200 are isolated.

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

Output: 9

The run 0 through 8 has length 9; the duplicate 0 does not extend it.

How this uses the pattern

Drop everything into a hash set. Then only begin counting a run at a number whose predecessor is absent, so each run is measured exactly once. That guard is what makes it O(n) instead of O(n log n).

Longest Consecutive Sequence: Hash Set Run-Starts

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[100,4,200,1,3,2]]Expected: 4

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

Input: [[]]Expected: 0

Input: [[1,2,0,1]]Expected: 3

Need a hint? (3 available)

The Google angle

Sorting solves this in O(n log n), and it works. So the real question is whether you can get to O(n). Google asks for linear time outright, which kills the sort. The whole solve hinges on one guard: only count upward from a number whose predecessor n - 1 is absent from the set. Most people see a loop inside a loop and assume it's quadratic. Explain why that guard keeps the total work linear, because the Doc won't run it to prove you right.

Take it further

What if you need the run itself, not just its length, and ties go to the smallest starting value? Track the best length together with its start. When a new run ties the current best, keep the one whose start is smaller. The run is then range(start, start + best_length), since the set guarantees every value in between is present.

Show solution & walkthrough

3

Valid Parentheses: Stack Matching

EasyCommonly asked

Problem

Given a string s of the characters (, ), {, }, [ and ], decide whether it is valid. It is valid when every closer matches the most recent unmatched opener of the same type, and every opener is eventually closed.

Input: s = "()[]{}"

Output: true

Each closer matches the opener directly before it.

Input: s = "([)]"

Output: false

The brackets cross instead of nesting: the ) tries to close a [.

Input: s = "{[]}"

Output: true

Properly nested: the inner [] closes before the outer {}.

How this uses the pattern

Push every opener onto a stack. On a closer, the matching opener must be on top: pop and compare. If the top is wrong or the stack is empty, it is invalid. A non-empty stack at the end means unclosed openers.

Valid Parentheses: Stack Matching

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: "()[]{}"Expected: True

Input: "([)]"Expected: False

Input: "{[]}"Expected: True

Input: "]"Expected: False

Input: "("Expected: False

Need a hint? (3 available)

The Google angle

This is the canonical stack problem, so Google uses it to confirm you reach for a stack the instant you see nesting, often phrased as "validate that these nested config blocks open and close correctly." The follow-up ladder is the interesting part: the minimum insertions or deletions to make the string valid, or balancing a string that also contains wildcards. State the invariant, that the stack holds exactly the openers still waiting, because the Doc gives no other proof.

Take it further

What is the minimum number of brackets to insert to make the string valid? Track two counters instead of a stack: open_needed, the unmatched closers that need an opener inserted before them, and open_count, the openers still waiting. Each unmatchable closer bumps open_needed; whatever openers remain at the end each need a closer. The answer is their sum.

Show solution & walkthrough

4

Maximal Rectangle: Monotonic Stack

HardSometimes asked

Problem

Given a binary matrix of '0' and '1' characters, find the largest rectangle made entirely of '1's and return its area.

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output: 6

The 2-by-3 block in the bottom-left region of the dense rows has area 6.

Input: matrix = [["0"]]

Output: 0

No 1s, so no rectangle.

How this uses the pattern

Treat each row as the ground of a histogram: heights[c] is the count of consecutive 1s ending at this row in column c. The answer is the largest rectangle across all those histograms, and each histogram is solved with a monotonic stack.

Maximal Rectangle: Monotonic Stack

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]]Expected: 6

Input: [[["0"]]]Expected: 0

Input: [[["1"]]]Expected: 1

Input: [[["1","1"],["1","1"]]]Expected: 4

Need a hint? (3 available)

The Google angle

This is the Google-flavored Hard in this group, and it is built from two pieces: a row-by-row height sweep, and the Largest Rectangle in Histogram subroutine underneath. Interviewers ladder up to it. They may start you on the plain histogram problem, confirm the monotonic stack, then reveal the matrix wrapper. It's all decomposition: say that maximal rectangle is "largest histogram rectangle, run once per row" and you've done most of the solve. Explain why each bar is pushed and popped exactly once, because the Doc won't run it for you.

Take it further

What if you want the largest all-1s square instead of any rectangle? Switch to a small dynamic-programming table: dp[r][c] is the side of the largest square whose bottom-right corner is (r, c), computed as 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) when the cell is a 1. The answer is the largest side squared. That is O(rows times cols) with no stack at all.

Show solution & walkthrough

Strings and simulation

String and simulation problems are graded on care. There's rarely a slick algorithm to find. The difficulty is in the bookkeeping. An off-by-one in the spacing, a last line that behaves differently, the single-word input nobody planned for. Google reaches for these to see whether your code survives contact with the messy details.

Two skills carry most of them. Parse the input cleanly so stray whitespace never bites you. The other is spreading a fixed number of spaces across a fixed number of gaps: do the division once, then hand the remainder out one unit at a time. Get those right and the rest is following the spec.

How Google frames strings

Because the algorithm is simple, Google watches your edge-case discipline instead. In Text Justification the last line is left-justified, a single-word line pads on the right, and uneven spaces favor the left gaps. Miss any one and the output is wrong. The escalation trades the easy greedy approach for an optimal one that breaks the lines to minimize total raggedness with a DP. The base problem is about getting every space right. The twist is spotting the optimization hiding under it.

The two moves to know

Almost every problem here mixes these two.

Pattern 1: Parse, then rebuild

Don't fight raw whitespace; tokenize first. Python's split() with no argument drops every run of spaces and ignores leading and trailing ones, leaving clean words. Then you rebuild the output with exactly the spacing the problem wants.

def normalize(text):
    words = text.split()       # splits on any run of whitespace; no empty tokens
    return ' '.join(words)     # rebuild with exactly one space between words

Separate parsing from formatting and the problem shrinks. Once words is a clean list, every spacing decision is arithmetic on its length, with no stray-space special cases left to trip on.

Pattern 2: Distribute with a remainder

Spreading N spaces across K gaps as evenly as possible is one divmod. Every gap gets the quotient; the remainder is handed out one extra unit at a time, to the leftmost gaps first (the convention full justification uses).

def distribute(total, gaps):
    base, extra = divmod(total, gaps)   # base per gap; 'extra' units left over
    # the first 'extra' gaps get one more than the rest
    return [base + (1 if i < extra else 0) for i in range(gaps)]

These are pure implementation problems, less algorithm than care; the Foundations course covers the string and array basics. Here we'll nail the spec and the edges.

String problems asked at Google

Two problems: the gentle distribute-with-remainder, then the full justification that adds line breaking on top. Read the spec twice and list the edge cases before you type.

5

Rearrange Spaces: Even Distribution

EasyRarely asked

Problem

Given a string text of words separated by one or more spaces (with possible leading or trailing spaces), redistribute the spaces so the same maximal number sits between every pair of adjacent words, with any leftover spaces appended at the end. If there is only one word, all the spaces go after it.

Input: text = " this is a sentence "

Output: "this is a sentence"

9 spaces, 3 gaps: 3 per gap, 0 left over.

Input: text = " practice makes perfect"

Output: "practice makes perfect "

7 spaces, 2 gaps: 3 per gap, 1 trailing.

How this uses the pattern

Count the total spaces, split into words, then divmod(spaces, gaps): base spaces between each pair, remainder trailing. One word means every space trails it.

Rearrange Spaces: Even Distribution

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: " this is a sentence "Expected: "this is a sentence"

Input: " practice makes perfect"Expected: "practice makes perfect "

Input: " hello "Expected: "hello "

Need a hint? (3 available)

The Google angle

Rearrange Spaces is the gentle cousin of Text Justification. Same distribute-with-remainder math, minus the line breaking. Google's natural twist is to push the leftover spaces into the leftmost gaps instead of trailing them, which is exactly how full justification spreads its spaces.

Take it further

Leftovers to the left: spread the remainder into the leftmost gaps (the way full justification does) rather than trailing them. Same base, extra = divmod(spaces, gaps), but give the first extra gaps one more space each and leave nothing at the end.

Show solution & walkthrough

6

Text Justification: Greedy Fill

HardSometimes asked

Problem

Given an array of words and a width maxWidth, format the text so every line is exactly maxWidth characters and fully justified. Greedily pack as many words per line as fit, distribute spaces between them as evenly as possible with any extras going to the leftmost gaps, and left-justify the final line. A line holding a single word is left-justified (padded on the right).

Input: words = ["This","is","an","example","of","text","justification."], maxWidth = 16

Output: ["This is an","example of text","justification. "]

Each non-final line is padded to 16; the last line is left-justified.

How this uses the pattern

Two phases. Greedily group words into lines (a word fits if current length + word lengths + one space between each <= width), then justify each line by spreading the leftover spaces across its gaps with divmod.

Text Justification: Greedy Fill

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: ["This","is","an","example","of","text","justification."], 16Expected: ["This is an", "example of text", "justification. "]

Input: ["What","must","be","acknowledgment","shall","be"], 16Expected: ["What must be", "acknowledgment ", "shall be "]

Need a hint? (3 available)

The Google angle

Text Justification is pure simulation, so Google uses it to watch your edge-case discipline. The last line is left-justified, a single-word line pads on the right, and uneven spaces favor the left gaps. The escalation drops the greedy approach for optimal line breaking, minimizing total raggedness with a DP.

Take it further

Minimum raggedness: instead of greedily filling each line, choose line breaks that minimize total "badness," the sum of squared trailing spaces with the last line free. A DP over word indices does it: dp[i] is the best layout of words[i:], trying every possible line-ending word j.

Show solution & walkthrough