Array & String Basics

Problem: Convert a Roman numeral (I V X L C D M = 1, 5, 10, 50, 100, 500, 1000) to an integer. IV = 4, IX = 9, XL = 40, etc.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 15 · s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M'). · It is guaranteed that s is a valid roman numeral in the range [1, 3999].

From brute force to the pattern: Listing all six subtractive pairs as special cases works but is clumsy. The "smaller before larger" rule handles them all in one scan: O(n).

Spot it: A lookup table (symbol → value) plus one left-to-right scan. The only rule: a symbol written before a larger one is subtracted; otherwise it is added.

Approach:

1. Map each symbol to its value.
2. For each position i: if the next symbol is larger, subtract this value; otherwise add it.
3. Return the total.

class Solution:
    def romanToInt(self, s: str) -> int:
        value = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        total = 0
        for i in range(len(s)):
            current = value[s[i]]
            if i + 1 < len(s) and value[s[i + 1]] > current:
                total = total - current     # e.g. the I in IV
            else:
                total = total + current
        return total

What the code is doing, line by line:

1. value: the seven symbols.
2. if i + 1 < len(s) and value[s[i + 1]] > current: a smaller symbol before a larger one, as in IV, IX or CM, is subtracted.
3. else: total = total + current: the normal case, including the last symbol.

Dry run on the example:

s = "MCMXCIV" (LeetCode Example 3). Returns 1994.

symbol	value	next is bigger?	total
M	1000	no → add	1000
C	100	yes (M) → subtract	900
M	1000	no → add	1900
X	10	yes (C) → subtract	1890
C	100	no → add	1990
I	1	yes (V) → subtract	1989
V	5	no → add	1994

Edge cases to test:

• A single symbol.
• Subtractive pairs at the end, e.g. "XIV".
• The largest value, "MMMCMXCIX" (3999).

Complexity: O(n) time, O(1) space.

Problem: Return the longest prefix shared by all strings in strs, or "" if there is none.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ strs.length ≤ 200 · 0 ≤ strs[i].length ≤ 200 · strs[i] consists of only lowercase English letters if it is non-empty.

From brute force to the pattern: Taking every prefix of the first string and checking it against all others is O(L² · n). Vertical scanning stops at the first mismatch: O(total characters).

Spot it: Vertical scanning: check character i of every string before moving to i + 1. The prefix can't be longer than the shortest string.

Approach:

1. For each index i of the first string: take ch = strs[0][i].
2. If any other string is too short or has a different character at i, the prefix is strs[0][:i].
3. If the loop finishes, the whole first string is the prefix.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        first = strs[0]
        for i in range(len(first)):
            ch = first[i]
            for word in strs[1:]:
                if i == len(word) or word[i] != ch:
                    return first[:i]      # column i is not shared by everyone
        return first

What the code is doing, line by line:

1. first = strs[0]: any common prefix is a prefix of the first string.
2. for i in range(len(first)): column by column.
3. if i == len(word) or word[i] != ch: word ran out, or disagrees. The check i == len(word) comes first so word[i] is never out of range.
4. return first[:i]: characters 0..i − 1 were shared by all.

Dry run on the example:

strs = ["flower", "flow", "flight"] (LeetCode Example 1). Returns "fl".

i	ch	flow	flight	result
0	f	f ✓	f ✓	continue
1	l	l ✓	l ✓	continue
2	o	o ✓	i ✗	return "fl"

Edge cases to test:

• A single string → itself.
• An empty string in the list → "".
• No common prefix → "".

Complexity: O(S) time where S is the total number of characters, O(1) extra space.

Problem: Write s in a zigzag on numRows rows (down the rows, then diagonally back up, repeating), then read the rows left to right. Return that string.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 1000 · s consists of English letters (lower-case and upper-case), ',' and '.'. · 1 ≤ numRows ≤ 1000

From brute force to the pattern: Building a full 2-D grid of the zigzag wastes space. One list per row and a bouncing row index is O(n) (a formula for each row's indices also works).

Spot it: A direct simulation: one string builder per row, and a pointer that bounces between the top and bottom rows.

Approach:

1. If numRows is 1 (or at least len(s)), the zigzag is just s.
2. Keep rows = [""] * numRows, a current row, and a direction step (+1 down, −1 up).
3. Append each character to rows[row]. Flip the direction at the top and bottom rows, then move.
4. Join the rows.

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s
        rows = [[] for _ in range(numRows)]
        row = 0
        step = 1                      # +1 = moving down, -1 = moving up
        for ch in s:
            rows[row].append(ch)
            # bounce off the top and bottom rows
            if row == 0:
                step = 1
            elif row == numRows - 1:
                step = -1
            row = row + step
        return "".join("".join(r) for r in rows)

What the code is doing, line by line:

1. if numRows == 1 ...: with one row the direction would never change and row would run off the end, so return early.
2. rows = [[] for _ in range(numRows)]: a separate list of characters for each row.
3. if row == 0: step = 1 / elif row == numRows - 1: step = -1: change direction at the edges after writing there.
4. "".join("".join(r) for r in rows): read row 0, then row 1, and so on.

Dry run on the example:

s = "PAYPALISHIRING", numRows = 3 (LeetCode Example 1). Returns "PAHNAPLSIIGYIR".

row	characters written to it, in order
0	P A H N
1	A P L S I I G
2	Y I R

The row index goes 0 1 2 1 0 1 2 1 0 …. Reading the rows gives PAHN + APLSIIG + YIR.

Edge cases to test:

• numRows = 1 → the string itself.
• numRows ≥ the length → the string itself.
• Two rows.

Complexity: O(n) time and space.

Problem: Return the number in nums closest to 0. If there is a tie (like -2 and 2), return the larger one.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ n ≤ 1000 · -10⁵ ≤ nums[i] ≤ 10⁵

From brute force to the pattern: Sorting by distance is O(n log n). One pass with a tie-break rule is O(n).

Spot it: A single best-so-far scan. The only subtlety is the tie-break, so compare by distance first and by value second.

Approach:

1. Start with closest = nums[0].
2. For each x: it wins if abs(x) < abs(closest), or if the distances tie and x > closest.
3. Return closest.

class Solution:
    def findClosestNumber(self, nums: List[int]) -> int:
        closest = nums[0]
        for x in nums:
            if abs(x) < abs(closest):
                closest = x                   # strictly nearer to zero
            elif abs(x) == abs(closest) and x > closest:
                closest = x                   # same distance: prefer the positive one
        return closest

What the code is doing, line by line:

1. closest = nums[0]: a real element to compare against (not 0, which might not be in the array).
2. abs(x) < abs(closest): distance to zero is the absolute value.
3. elif abs(x) == abs(closest) and x > closest: a tie can only be −v vs v; keep the larger, v.

Dry run on the example:

nums = [-4, -2, 1, 4, 8] (LeetCode Example 1). Returns 1.

x	|x|	|closest|	closest after
−4	4	4	−4 (same number)
−2	2	4	−2
1	1	2	1
4	4	1	1
8	8	1	1

Edge cases to test:

• A tie between -x and x → x.
• All negative numbers.
• Zero present → 0.

Complexity: O(n) time, O(1) space.

Problem: s has words separated by spaces (possibly with extra spaces anywhere). Return the length of the last word.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 10⁴ · s consists of only English letters and spaces ' '. · There will be at least one word in s.

From brute force to the pattern: s.split()[-1] builds a list of every word: O(n) time and space. Scanning from the end touches only the last word and the trailing spaces.

Spot it: Only the end of the string matters, so read it backwards instead of splitting the whole string.

Approach:

1. Start i at the last index and move left past any trailing spaces.
2. Then count characters moving left until a space or the start of the string.

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        i = len(s) - 1
        # skip spaces at the end
        while i >= 0 and s[i] == " ":
            i = i - 1
        length = 0
        # count letters of the last word
        while i >= 0 and s[i] != " ":
            length = length + 1
            i = i - 1
        return length

What the code is doing, line by line:

1. i = len(s) - 1: the last character.
2. First loop: "fly me to the moon " ends with spaces that aren't part of any word.
3. Second loop: count until the space before the word (or index −1).
4. Checking i >= 0 first prevents reading s[-1], which in Python would wrap around to the last character.
5. One-liner alternative: len(s.split()[-1]), which builds a list of all words.

Dry run on the example:

s = " fly me to the moon " (LeetCode Example 2). Returns 4.

phase	characters passed	length
skip trailing spaces	2 spaces	0
count	n, o, o, m	4
stop	space before moon	4

Edge cases to test:

• Trailing spaces, e.g. "moon ".
• A single word.
• Spaces at the start.

Complexity: O(n) time in the worst case, O(1) space.

Problem: Return the index of the first occurrence of needle in haystack, or -1 if needle isn't part of it.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ haystack.length, needle.length ≤ 10⁴ · haystack and needle consist of only lowercase English characters.

From brute force to the pattern: Slicing and comparing at every start is O((n − m + 1) · m) in the worst case, which is fine here. KMP or rolling hashes avoid re-comparing characters.

Spot it: A fixed-length window (the length of needle) slid across haystack, comparing at each start. KMP gets O(n + m), but the straightforward scan is what interviews expect first.

Approach:

1. For every start i from 0 to n − m: compare haystack[i : i + m] with needle.
2. Return the first i that matches; -1 if none.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        m = len(needle)
        for i in range(n - m + 1):
            # compare the window that starts at i, character by character
            j = 0
            while j < m and haystack[i + j] == needle[j]:
                j = j + 1
            if j == m:
                return i              # every character matched
        return -1

What the code is doing, line by line:

1. range(n - m + 1): the last start that still leaves room for m characters is n − m.
2. Inner while: advance j while characters match; stop at the first mismatch.
3. if j == m: return i: the whole needle matched at start i.
4. Python's built-in haystack.find(needle) does the same job.

Dry run on the example:

haystack = "leetcode", needle = "leeto" (LeetCode Example 2). Returns -1.

start i	window	matched before mismatch	result
0	"leetc"	leet (4), then c ≠ o	no
1	"eetco"	0 (e ≠ l)	no
2	"etcod"	0	no
3	"tcode"	0	no → −1

Edge cases to test:

• The needle longer than the haystack → −1.
• A match at the very start or end.
• Repetitive text, e.g. "aaaa" / "aab".

Complexity: O((n − m + 1) · m) time in the worst case, O(1) space.

Problem: Convert an integer 1..3999 to a Roman numeral.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ num ≤ 3999

From brute force to the pattern: Handling each decimal digit with special cases is error-prone. A 13-entry table and greedy subtraction is simple and O(1) for numbers up to 3999.

Spot it: List every symbol value including the subtractive forms (CM 900, CD 400, XC 90, XL 40, IX 9, IV 4), largest first. Then greedily take the biggest value that still fits, like making change with coins.

Approach:

1. Keep a list of (value, symbol) pairs from 1000 down to 1.
2. For each pair: while num ≥ value, append the symbol and subtract the value.
3. Join the pieces.

class Solution:
    def intToRoman(self, num: int) -> str:
        table = [(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
                 (100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
                 (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")]
        parts = []
        for value, symbol in table:
            # take this symbol as many times as it fits
            while num >= value:
                parts.append(symbol)
                num = num - value
        return "".join(parts)

What the code is doing, line by line:

1. table: the 7 basic symbols plus the 6 subtractive pairs, in decreasing order. Including the pairs is what makes greedy correct (otherwise 4 would become IIII).
2. while num >= value: use the largest value as many times as possible before moving to a smaller one.
3. "".join(parts): concatenate the symbols.

Dry run on the example:

num = 1994 (LeetCode Example 3). Returns "MCMXCIV".

value used	symbol	num left	so far
1000	M	994	M
900	CM	94	MCM
90	XC	4	MCMXC
4	IV	0	MCMXCIV

Edge cases to test:

• 4 → "IV", 9 → "IX".
• 3999 → "MMMCMXCIX".
• Numbers with zeros, e.g. 1004 → "MIV".

Complexity: O(1): the numeral is at most 15 symbols for numbers up to 3999.

Problem: Reverse the order of the words in s. The result must have exactly one space between words and no leading or trailing spaces, even if s has extra spaces.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 10⁴ · s contains English letters (upper-case and lower-case), digits, and spaces ' '. · There is at least one word in s.

From brute force to the pattern: Repeatedly finding and removing the last word is O(n²). One scan to collect words, a reverse and a join is O(n) (" ".join(reversed(s.split()))).

Spot it: Extract the words with a manual scan (or s.split(), which already drops extra spaces), then output them in reverse. That's string parsing, not a pattern.

Approach:

1. Scan s: skip spaces; when a letter starts, read to the end of the word and save it.
2. Reverse the list of words.
3. Join them with single spaces.

class Solution:
    def reverseWords(self, s: str) -> str:
        words = []
        i = 0
        n = len(s)
        while i < n:
            if s[i] == " ":
                i = i + 1                 # skip any number of spaces
                continue
            start = i
            while i < n and s[i] != " ":
                i = i + 1                 # read to the end of the word
            words.append(s[start:i])
        words.reverse()
        return " ".join(words)

What the code is doing, line by line:

1. Outer while: walks the whole string once.
2. if s[i] == " ": ... continue: leading, trailing and repeated spaces are all skipped here.
3. start = i and the inner loop: find where the word ends; s[start:i] is the word.
4. words.reverse(), then " ".join(words): one space between words, none at the ends.
5. Shortcut: " ".join(reversed(s.split())) does all of this in one line.

Dry run on the example:

s = " hello world " (LeetCode Example 2). Returns "world hello".

step	words
skip 2 spaces, read hello	["hello"]
skip 1 space, read world	["hello", "world"]
skip 2 trailing spaces	["hello", "world"]
reverse + join	"world hello"

Edge cases to test:

• Leading and trailing spaces.
• Several spaces between words.
• A single word.

Complexity: O(n) time and space.

Problem: Implement myAtoi: skip leading spaces, optional sign, read digits until a non-digit, clamp to [−2³¹, 2³¹ − 1].

Solve it on LeetCode ↗

Constraints: 0 ≤ s.length ≤ 200 · s consists of English letters (lower-case and upper-case), digits (0 - 9), ' ', '+', '-', and '.'.

From brute force to the pattern: There's no shortcut; the point is handling every phase correctly.

Spot it: A careful left-to-right parse (a tiny state machine): whitespace → sign → digits → stop. The only trap is the order of checks.

Why not another pattern? Regex or int() on slices hides the edge cases the interviewer is testing.

Approach:

1. Skip spaces.
2. Read +/− once.
3. Accumulate digits; stop at the first non-digit.
4. Apply the sign and clamp.

class Solution:
    def myAtoi(self, s: str) -> int:
        i, n = 0, len(s)
        while i < n and s[i] == " ":
            i += 1  # leading spaces
        sign = 1
        if i < n and s[i] in "+-":
            sign = -1 if s[i] == "-" else 1  # at most one sign
            i += 1
        value = 0
        while i < n and s[i].isdigit():
            value = value * 10 + int(s[i])
            i += 1
        value *= sign
        return max(-2**31, min(2**31 - 1, value))  # clamp to 32-bit

What the code is doing, line by line:

1. Anything after the digits is ignored, including more digits after a letter.
2. Python integers don't overflow, so clamping once at the end is safe (in Java/C++ check before multiplying).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• " -42"
• "words 987" → 0.
• Overflow both ways.
• "+-12" → 0.

Complexity: O(n) time, O(1) space.

Problem: Term 1 is "1"; each next term reads the previous one aloud as (count, digit) pairs. Return term n.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 30

From brute force to the pattern: Simulation is the intended solution.

Spot it: Each step is run-length encoding: group equal consecutive digits and write count then digit.

Why not another pattern? There's no closed form; simulation is the solution.

Approach:

1. term = "1".
2. Repeat n − 1 times: scan runs, append str(run length) + digit.

class Solution:
    def countAndSay(self, n: int) -> str:
        term = "1"
        for _ in range(n - 1):
            out = []
            i = 0
            while i < len(term):
                j = i
                while j < len(term) and term[j] == term[i]:
                    j += 1  # end of this run of equal digits
                out.append(str(j - i) + term[i])  # "how many" then "which digit"
                i = j
            term = "".join(out)
        return term

What the code is doing, line by line:

1. j moves to the end of each run; the run length is j − i.
2. Joining a list avoids quadratic string building.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → "1".
• Runs of three ("111" → "31").
• Larger n (fast growth).

Complexity: O(total length of all terms); terms grow about 30% per step.

Problem: Multiply two non-negative integers given as strings, without converting them to integers directly.

Solve it on LeetCode ↗

Constraints: 1 ≤ num1.length, num2.length ≤ 200 · num1 and num2 consist of digits only. · Both num1 and num2 do not contain any leading zero, except the number 0 itself.

From brute force to the pattern: Summing n shifted partial products as strings works but is clumsier; the position array does it directly.

Spot it: Grade-school multiplication on digit arrays: the product of num1[i] and num2[j] contributes to positions i + j and i + j + 1 of a result array of length m + n.

Why not another pattern? int(num1) * int(num2) is forbidden; repeated string addition is slower.

Approach:

1. res = [0] * (m + n).
2. For i, j from the right: total = d1 · d2 + res[i + j + 1]; res[i + j + 1] = total % 10; res[i + j] += total // 10.
3. Strip leading zeros.

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        m, n = len(num1), len(num2)
        res = [0] * (m + n)  # the product has at most m + n digits
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                total = int(num1[i]) * int(num2[j]) + res[i + j + 1]
                res[i + j + 1] = total % 10  # this position's digit
                res[i + j] += total // 10  # carry to the left
        digits = "".join(map(str, res)).lstrip("0")
        return digits or "0"

What the code is doing, line by line:

1. Digit i from the left of a length-m number has place value 10^(m−1−i); the product lands at index i + j + 1 from the left.
2. Carries are pushed one position left right away.
3. An all-zero result becomes "0".

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A zero operand → "0".
• Carries spreading left.
• Single digits.

Complexity: O(m · n) time, O(m + n) space.

Problem: Return "IPv4", "IPv6" or "Neither" for a query string.

Solve it on LeetCode ↗

Constraints: queryIP consists only of English letters, digits and the characters '.' and ':'.

From brute force to the pattern: There's no shortcut: precise validation is the task.

Spot it: A parsing problem: split on . or : and validate each part (digits, ranges, leading zeros, hex length).

Why not another pattern? int() alone accepts signs, spaces and leading zeros that are invalid here.

Approach:

1. IPv4: 4 parts, each 1–3 digits, no leading zero unless "0", value ≤ 255.
2. IPv6: 8 parts, each 1–4 hex digits.
3. Otherwise "Neither".

class Solution:
    def validIPAddress(self, queryIP: str) -> str:
        parts = queryIP.split(".")
        if len(parts) == 4 and all(
            p.isdigit() and p.isascii() and len(p) <= 3 and (p == "0" or p[0] != "0") and int(p) <= 255
            for p in parts
        ):
            return "IPv4"  # four decimal numbers 0-255, no leading zeros
        groups = queryIP.split(":")
        hexdigits = set("0123456789abcdefABCDEF")
        if len(groups) == 8 and all(1 <= len(g) <= 4 and set(g) <= hexdigits for g in groups):
            return "IPv6"  # eight groups of 1-4 hex digits
        return "Neither"

What the code is doing, line by line:

1. isdigit() rejects signs and spaces; isascii() rejects other Unicode digits.
2. A part like "01" is invalid in IPv4 but "0" is fine.
3. IPv6 groups allow leading zeros but at most 4 characters.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Leading zeros in IPv4.
• Empty parts ("1..1.1").
• Five-character IPv6 group.

Complexity: O(n) time and space.

Problem: Return the minimum number of times to repeat a so that b is a substring of it, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ a.length, b.length ≤ 10⁴ · a and b consist of lowercase English letters.

From brute force to the pattern: Growing the repeat count without a bound can loop forever; two checks suffice.

Spot it: If b fits anywhere, it starts within the first copy of a, so it ends within ceil(len(b)/len(a)) + 1 copies. Only two candidates need a substring search.

Why not another pattern? Repeating more and more copies without a bound never terminates for impossible inputs.

Approach:

1. q = ceil(len(b) / len(a)).
2. If b in a * q, return q; if b in a * (q + 1), return q + 1; else −1.

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        q = -(-len(b) // len(a))  # ceil: copies needed just to be long enough
        for times in (q, q + 1):  # b can start anywhere in the first copy
            if b in a * times:
                return times
        return -1

What the code is doing, line by line:

1. b must start at some offset inside the first copy of a (later starts repeat earlier ones).
2. From that offset, q + 1 copies always cover all of b.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• b shorter than a.
• Characters of b not in a → −1.
• b needs to wrap around a copy boundary.

Complexity: O((m + n) · n) with naive search, O(m + n) with KMP.

Problem: On an infinite grid, can you reach target before any ghost (moving optimally) can catch you?

Solve it on LeetCode ↗

Constraints: 1 ≤ ghosts.length ≤ 100 · ghosts[i].length == 2 · -10⁴ ≤ xi, yi ≤ 10⁴ · There can be multiple ghosts in the same location. · target.length == 2 · -10⁴ ≤ xtarget, ytarget ≤ 10⁴

From brute force to the pattern: Game simulation is unnecessary; the distance comparison is exact.

Spot it: A ghost's best strategy is to go straight to the target and wait. So it's a comparison of Manhattan distances; no simulation needed.

Why not another pattern? Simulating moves on an infinite grid is pointless; intercepting earlier is never better for a ghost than waiting at the target.

Approach:

1. mine = |tx| + |ty|.
2. Escape iff every ghost has |gx − tx| + |gy − ty| > mine.

class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        tx, ty = target
        mine = abs(tx) + abs(ty)
        return all(abs(gx - tx) + abs(gy - ty) > mine for gx, gy in ghosts)  # every ghost arrives later

What the code is doing, line by line:

1. If a ghost could catch you anywhere on your route, it could also reach the target no later than you (triangle inequality).
2. Ties count as being caught, hence the strict >.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A ghost exactly as far as you → false.
• A ghost at the target.
• Several ghosts at one spot.

Complexity: O(g) time, O(1) space.

Problem: Even → divide by 2; odd → add 1. Count steps to reach 1 for a binary string (up to 500 bits).

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 500 · s consists of characters '0' or '1' · s[0] == '1'

From brute force to the pattern: Big-integer simulation is O(n²) bit operations; the carry scan is O(n).

Spot it: Simulate on the bits from the right, tracking the carry from +1: an effective 0 bit costs 1 step (divide); an effective 1 costs 2 (add 1, making a carry, then divide).

Why not another pattern? Converting to an int works in Python, but the bit-level reasoning is what interviews look for (and works in any language).

Approach:

1. steps = 0, carry = 0; for i from the last bit down to index 1:
2. bit = int(s[i]) + carry; bit == 1 → steps += 2, carry = 1; else steps += 1 (carry unchanged).
3. Return steps + carry (a final carry turns the leading 1 into 10, needing one more division).

class Solution:
    def numSteps(self, s: str) -> int:
        steps = 0
        carry = 0
        for i in range(len(s) - 1, 0, -1):  # every bit except the leading 1
            bit = int(s[i]) + carry
            if bit == 1:
                steps += 2  # odd: add 1 (carry), then divide
                carry = 1
            else:
                steps += 1  # even (0, or 1 + carry = 2): just divide
        return steps + carry  # a leftover carry makes "10": one more division

What the code is doing, line by line:

1. Each loop iteration removes one bit (one division), plus one addition when the bit is effectively 1.
2. Once a carry exists it never disappears until the top, because 1 + 1 = 10 propagates.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• "1" → 0.
• All ones.
• A power of two.

Complexity: O(n) time, O(1) space.

Problem: S1 = "0", Sn = S(n−1) + "1" + reverse(invert(S(n−1))). Return the k-th bit of Sn.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 20 · 1 ≤ k ≤ 2n - 1

From brute force to the pattern: Building the whole string is O(2ⁿ); the index walk is O(n).

Spot it: Sn has length 2ⁿ − 1 with "1" in the middle. The left half is S(n−1), and position k in the right half mirrors position 2ⁿ − k of the left half, inverted → a divide-and-conquer index walk, no string building.

Why not another pattern? Building S20 (about a million characters) works but wastes memory; the recursion is O(n).

Approach:

1. mid = 2^(n−1). If k == mid: "1".
2. If k < mid: answer in S(n−1) at k.
3. Else: invert the answer for S(n−1) at 2ⁿ − k.

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        flip = 0
        while n > 1:
            mid = 1 << (n - 1)
            if k == mid:
                return "1" if flip == 0 else "0"  # the middle bit is 1
            if k > mid:
                k = (1 << n) - k  # mirror into the left half
                flip ^= 1  # the right half is inverted
            n -= 1
        return "0" if flip == 0 else "1"  # S1 = "0"

What the code is doing, line by line:

1. The loop replaces recursion: each step moves to S(n−1), remembering whether the bit is inverted.
2. Position k in the right half corresponds to position 2ⁿ − k in the left half (the reversal).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k is the middle.
• n = 1.
• k in the far right (many inversions).

Complexity: O(n) time, O(1) space.

Problem: Given a palindrome, return its lexicographically smallest palindromic permutation.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s consists of lowercase English letters. · s is guaranteed to be palindromic.

From brute force to the pattern: All permutations is factorial; sorting the half is O(n log n).

Spot it: A palindrome is decided by its first half. The smallest first half is the half's letters sorted; the middle (odd length) is forced.

Why not another pattern? Generating permutations is factorial.

Approach:

1. half = sorted(s[:n // 2]).
2. Return half + middle + reversed(half).

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        n = len(s)
        half = "".join(sorted(s[:n // 2]))  # the first half determines everything
        middle = s[n // 2] if n % 2 else ""
        return half + middle + half[::-1]

What the code is doing, line by line:

1. The first half of a palindrome contains exactly half of each letter's count.
2. For odd length, the middle letter is the one with an odd count, already in the middle of s.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Length 1.
• All the same letter.
• Odd length (the middle stays).

Complexity: O(n log n) time (or O(n) with counting), O(n) space.

Problem: Fully justify words into lines of exactly maxWidth characters; the last line and single-word lines are left-justified.

Solve it on LeetCode ↗

Constraints: 1 ≤ words.length ≤ 300 · 1 ≤ words[i].length ≤ 20 · words[i] consists of only English letters and symbols · 1 ≤ maxWidth ≤ 100 · words[i].length ≤ maxWidth

From brute force to the pattern: This is a careful simulation; there's no faster trick.

Spot it: Greedy packing: put as many words on a line as fit (with one space between). Then distribute the remaining spaces with divmod, giving the leftmost gaps one extra.

Why not another pattern? Any smarter line breaking (minimising raggedness) isn't what's asked; the problem specifies greedy.

Approach:

1. Collect words while letters + len(word) + gaps ≤ maxWidth.
2. Normal line: spaces, extra = divmod(maxWidth − letters, gaps); the first extra gaps get one more.
3. Last line or one word: join with single spaces and pad right.

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        lines = []
        i = 0
        while i < len(words):
            j = i
            letters = 0
            while j < len(words) and letters + len(words[j]) + (j - i) <= maxWidth:
                letters += len(words[j])  # fits with one space per gap
                j += 1
            line_words = words[i:j]
            gaps = j - i - 1
            if j == len(words) or gaps == 0:
                line = " ".join(line_words)
                lines.append(line + " " * (maxWidth - len(line)))  # left-justified
            else:
                spaces, extra = divmod(maxWidth - letters, gaps)
                line = ""
                for g, w in enumerate(line_words[:-1]):
                    line += w + " " * (spaces + (1 if g < extra else 0))  # leftmost gaps get the extra
                lines.append(line + line_words[-1])
            i = j
        return lines

What the code is doing, line by line:

1. (j − i) counts the minimum spaces needed between the words already chosen plus the new one.
2. divmod splits the spare spaces evenly; the remainder goes to the leftmost gaps.
3. The last line and single-word lines use one space between words and pad on the right.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A word exactly maxWidth long.
• A single word on a non-last line.
• The last line.

Complexity: O(total characters) time and space.

Problem: Add characters only in front of s to make the shortest palindrome.

Solve it on LeetCode ↗

Constraints: 0 ≤ s.length ≤ 5 * 10⁴ · s consists of lowercase English letters only.

From brute force to the pattern: Testing prefixes from longest to shortest is O(n²); KMP is O(n).

Spot it: Keep the longest palindromic prefix; reverse the rest and put it in front. That prefix is the longest prefix of s that's also a suffix of reverse(s) → the KMP prefix function of s + '#' + reverse(s).

Why not another pattern? Checking each prefix for being a palindrome is O(n²).

Approach:

1. t = s + '#' + s[::-1].
2. Compute the KMP failure array of t; L = fail[-1].
3. Return s[L:][::-1] + s.

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        t = s + "#" + s[::-1]  # '#' stops matches from crossing the middle
        fail = [0] * len(t)  # longest proper prefix that is also a suffix
        for i in range(1, len(t)):
            k = fail[i - 1]
            while k and t[i] != t[k]:
                k = fail[k - 1]  # fall back to a shorter border
            if t[i] == t[k]:
                k += 1
            fail[i] = k
        keep = fail[-1]  # length of the longest palindromic prefix of s
        return s[keep:][::-1] + s

What the code is doing, line by line:

1. A prefix of s equal to a suffix of reverse(s) reads the same backwards: it's a palindrome.
2. The separator keeps the border from being longer than s.
3. The characters after the palindromic prefix are mirrored in front.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already a palindrome → unchanged.
• Empty string.
• All characters distinct.

Complexity: O(n) time and space.

Problem: Return the k-th smallest distinct palindromic permutation of a palindrome s, or "" if there are fewer than k.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁴ · s consists of lowercase English letters. · s is guaranteed to be palindromic. · 1 ≤ k ≤ 10⁶

From brute force to the pattern: Enumerating arrangements up to k is O(k · n); group counting is O(26n).

Spot it: Choose the first half; it's a multiset permutation. Build it letter by letter: placing c first leaves P · cnt[c] / L arrangements (P = arrangements of the current multiset, L its size). Skip whole groups while k is larger, like Permutation Sequence.

Why not another pattern? Listing permutations up to k is O(k · n) and generating all is factorial.

Approach:

1. cnt[c] = half of each letter's count; L = Σ cnt; P = L! / Π cnt[c]!. If k > P, return "".
2. For each position: for letters c ascending with cnt[c] > 0: ways = P · cnt[c] // L. If k ≤ ways, take c; else k −= ways.
3. After taking c: P = ways, cnt[c] −= 1, L −= 1.
4. Return half + middle + reverse(half).

from collections import Counter
from math import factorial

class Solution:
    def smallestPalindrome(self, s: str, k: int) -> str:
        n = len(s)
        cnt = Counter(s[:n // 2])  # letters of the first half
        middle = s[n // 2] if n % 2 else ""
        L = n // 2
        P = factorial(L)
        for c in cnt.values():
            P //= factorial(c)  # distinct arrangements of the half
        if k > P:
            return ""
        half = []
        for _ in range(n // 2):
            for c in sorted(cnt):
                if cnt[c] == 0:
                    continue
                ways = P * cnt[c] // L  # arrangements that start with c
                if k <= ways:
                    half.append(c)
                    P = ways
                    cnt[c] -= 1
                    L -= 1
                    break
                k -= ways  # skip every arrangement starting with c
        h = "".join(half)
        return h + middle + h[::-1]

What the code is doing, line by line:

1. Fixing the first letter as c leaves a multiset with cnt[c] − 1 copies of c, whose arrangement count is P · cnt[c] / L.
2. Skipping all arrangements that start with a smaller letter is what makes this O(n · 26) instead of O(k).
3. Python's big integers keep P exact; it shrinks quickly as letters are placed.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Fewer than k palindromes → "".
• One distinct letter → only k = 1 works.
• Odd length (middle fixed).

Complexity: O(26 · n) big-integer steps, O(n) space.

Problem: Decide whether a string is a valid number: optional sign, digits with at most one dot, optionally e/E followed by a signed integer.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 20 · s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

From brute force to the pattern: Listing every pattern case by case is error-prone; three flags capture the grammar.

Spot it: A careful scan / state machine. Track whether you've seen digits, a dot and an exponent; each character is legal only in certain states. The exponent resets "seen digits" because it needs its own digits.

Why not another pattern? float(s) accepts things the problem rejects ("inf", "nan", underscores), and regex hides the rules being tested.

Approach:

1. Digit → digit = True.
2. +/− only at index 0 or right after e.
3. . only if no dot and no exponent yet.
4. e/E only once and only after a digit; then require new digits (digit = False).
5. Anything else → invalid. Valid if digit at the end.

class Solution:
    def isNumber(self, s: str) -> bool:
        seen_digit = seen_dot = seen_exp = False
        for i, ch in enumerate(s):
            if ch.isdigit():
                seen_digit = True
            elif ch in "+-":
                if i > 0 and s[i - 1] not in "eE":
                    return False  # a sign must be first, or right after the exponent
            elif ch == ".":
                if seen_dot or seen_exp:
                    return False  # one dot, and never inside the exponent
                seen_dot = True
            elif ch in "eE":
                if seen_exp or not seen_digit:
                    return False  # one exponent, with a number before it
                seen_exp = True
                seen_digit = False  # the exponent needs its own digits
            else:
                return False
        return seen_digit

What the code is doing, line by line:

1. .5, 5. and 5.5 are all valid; a lone . is not, because no digit was seen.
2. Resetting seen_digit after e rejects "1e".
3. isdigit() here only meets ASCII digits given the constraints.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• "." → false.
• "1e", "e3" → false.
• "-.9e+10" → true.

Complexity: O(n) time, O(1) space.

Problem: A robot repeats instructions G, L, R forever. Is it confined to a circle?

Solve it on LeetCode ↗

Constraints: 1 ≤ instructions.length ≤ 100 · instructions[i] is 'G', 'L' or, 'R'.

From brute force to the pattern: Simulating many passes doesn't prove anything; the one-pass test is exact.

Spot it: Simulate one pass. If the robot is back at the origin, it loops. If it faces a different direction, its displacements cancel within 4 passes. Only "moved and still facing north" escapes.

Why not another pattern? Simulating many passes and guessing is unreliable.

Approach:

1. Simulate once with a direction index.
2. Bounded iff position is (0, 0) or direction ≠ north.

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        x = y = 0
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # north, east, south, west
        d = 0
        for ch in instructions:
            if ch == "G":
                x += dirs[d][0]
                y += dirs[d][1]
            elif ch == "L":
                d = (d + 3) % 4
            else:
                d = (d + 1) % 4
        return (x, y) == (0, 0) or d != 0  # back home, or turning so the drift cancels out

What the code is doing, line by line:

1. Facing a new direction rotates the per-pass displacement; after 2 or 4 passes the rotations sum to zero.
2. Facing north with a non-zero displacement drifts away forever.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Only turns.
• Back at the origin after one pass.
• Straight line north.

Complexity: O(n) time, O(1) space.

Problem: In a sentence, discount every price word ($ followed by digits) by discount percent and format it with exactly two decimals.

Solve it on LeetCode ↗

Constraints: 1 ≤ sentence.length ≤ 10⁵ · sentence consists of lowercase English letters, digits, ' ', and '$'. · sentence does not have leading or trailing spaces. · All words in sentence are separated by a single space. · All prices will be positive numbers without leading zeros. · All prices will have at most 10 digits. · 0 ≤ discount ≤ 100

From brute force to the pattern: This is direct parsing; precision of the format check is the point.

Spot it: A word-by-word parse: check the exact price format, then compute and format. The trap is the format check ($, $1e5, 1$).

Why not another pattern? A loose regex or float() accepts words that aren't prices.

Approach:

1. Split by spaces.
2. Price iff w[0] == '$', len > 1, and w[1:] all digits.
3. New price int(w[1:]) · (100 − discount) / 100, formatted with :.2f.

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        words = sentence.split(" ")
        for i, w in enumerate(words):
            if len(w) > 1 and w[0] == "$" and w[1:].isdigit():  # exactly '$' + digits
                value = int(w[1:]) * (100 - discount) / 100
                words[i] = f"${value:.2f}"
        return " ".join(words)

What the code is doing, line by line:

1. isdigit() rejects signs, dots and letters.
2. Splitting on single spaces keeps the original spacing (the input has single spaces).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Lone $.
• $ inside a word.
• 100% discount → $0.00.

Complexity: O(n) time and space.

Problem: Using "reverse the whole array" and "rotate left by one", sort a permutation of 0..n−1 in the fewest operations, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ n - 1 · nums is a permutation of integers from 0 to n - 1.

From brute force to the pattern: BFS over permutations is factorial; the arithmetic is O(n).

Spot it: Both operations keep the circular adjacency, so only rotations of [0..n−1] or of [n−1..0] can be sorted. Then it's index arithmetic: count the rotations needed directly, with or without a reverse before or after.

Why not another pattern? BFS over permutations is factorial.

Approach:

1. Ascending rotation (nums[i] = (i + s) mod n): rotate left (n − s) mod n times, or reverse, rotate s times, reverse (s + 2).
2. Descending rotation (nums[i] = (c − i) mod n): rotate until n − 1 is first then reverse, or reverse first and rotate.
3. Otherwise −1.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        INF = float("inf")
        best = INF
        s = nums[0]
        if all(nums[i] == (i + s) % n for i in range(n)):  # a rotation of 0, 1, ..., n-1
            best = min(best, (n - s) % n)  # rotate until 0 is first
            if s:
                best = min(best, s + 2)  # reverse, rotate s times, reverse back
        c = nums[0]
        if all(nums[i] == (c - i) % n for i in range(n)):  # a rotation of n-1, ..., 1, 0
            t = (c - (n - 1)) % n  # rotations that bring n-1 to the front
            best = min(best, t + 1)  # ...then reverse
            r = [nums[n - 1 - i] for i in range(n)]  # reverse first
            best = min(best, 1 + (n - r[0]) % n)  # then rotate until 0 is first
        return best if best < INF else -1

What the code is doing, line by line:

1. Rotations and the full reversal never break the circle of neighbours, so the array must already be a rotation of sorted (or of reverse sorted).
2. For an ascending rotation starting at s, rotating left n − s times sorts it; alternatively reversing turns left rotations into right rotations, which costs s plus two reverses.
3. For a descending rotation, reverse exactly once: either after rotating n − 1 to the front, or first and then rotate.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already sorted → 0.
• Reversed → 1.
• Not a rotation → −1.

Complexity: O(n) time, O(n) space.

Problem: Convert a non-negative integer (< 2³¹) to English words.

Solve it on LeetCode ↗

Constraints: 0 ≤ num ≤ 2³¹ - 1

From brute force to the pattern: This is a careful simulation; the grouping keeps the special cases small.

Spot it: A careful string-building simulation: numbers are read in groups of three digits, each spelled the same way, followed by its scale word.

Why not another pattern? Handling every digit position separately leads to many special cases (teens, zeros).

Approach:

1. 0 → "Zero".
2. three(n): hundreds, then below 20 (one word) or tens + ones.
3. Peel groups with % 1000, attach Thousand / Million / Billion for non-zero groups.

class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"
        below_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve",
                    "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]

        def three(n):  # 1..999 as words
            words = []
            if n >= 100:
                words += [below_20[n // 100], "Hundred"]
                n %= 100
            if n >= 20:
                words.append(tens[n // 10])
                n %= 10
            if n:
                words.append(below_20[n])  # 1..19 have their own names
            return words

        words = []
        for scale in ["", "Thousand", "Million", "Billion"]:
            if num % 1000:
                words = three(num % 1000) + ([scale] if scale else []) + words  # this group goes in front
            num //= 1000
        return " ".join(words)

What the code is doing, line by line:

1. Every group of three digits is spelled identically, so one helper does all the work.
2. Groups that are all zeros add nothing (no "Zero Thousand").

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• 0 → Zero.
• Teens (Thirteen).
• Zero groups inside (1,000,010).

Complexity: O(1) (at most 10 digits).

Problem: Return the longest proper prefix of s that is also a suffix.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s contains only lowercase English letters.

From brute force to the pattern: Checking every prefix is O(n²); KMP (or a rolling hash) is O(n).

Spot it: That's exactly what the KMP prefix (failure) function computes for the whole string.

Why not another pattern? Comparing every prefix with the matching suffix is O(n²).

Approach:

1. Build fail where fail[i] = longest proper border of s[:i + 1].
2. Return s[:fail[-1]].

class Solution:
    def longestPrefix(self, s: str) -> str:
        fail = [0] * len(s)  # longest proper prefix of s[:i+1] that's also its suffix
        k = 0
        for i in range(1, len(s)):
            while k and s[i] != s[k]:
                k = fail[k - 1]  # fall back to a shorter border
            if s[i] == s[k]:
                k += 1
            fail[i] = k
        return s[:fail[-1]]

What the code is doing, line by line:

1. When the next character doesn't extend the current border, the next candidate is the border of the border.
2. Each step moves k forward at most once, so the total work is linear.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No happy prefix → "".
• All the same letter.
• Overlapping prefix and suffix.

Complexity: O(n) time and space.