Striver SDE Sheet Revision Notes

1 / 2

01A/191

Set Matrix Zero

Problem Statement

Given an m x n matrix, if any cell contains 0, set its complete row and complete column to 0. Return the final matrix after applying all such updates. In interviews, always clarify whether extra space is allowed or whether the matrix must be modified in-place.

Examples

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

Output: [[1,0,1],[0,0,0],[1,0,1]]

Explanation: Since matrix[1][1] is 0, row 1 and column 1 become 0.

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Explanation: Zeroes in row 0 force columns 0 and 3 to become 0 as well.

Custom Notes

Brute force teaches why direct zeroing is dangerous.
Better approach is easiest to explain under pressure.
Optimal approach reuses first row and first column as markers.
Collision point is matrix[0][0], so keep a separate col0 flag for the first column.
Memory hook: mark, scan, then zero from the markers.

Brute Force Approach : TC: SC:

1 / 3

Algorithm: Use a temporary marker value like -1 for cells that should later become 0.

Pseudo:

Traverse every cell in the matrix.
When matrix[i][j] == 0, mark all non-zero cells in row i as -1.
Mark all non-zero cells in column j as -1.
After the traversal, replace every -1 with 0.

Time: O(m*n*(m+n))

Space: O(1)

Why mention it: It clearly shows why changing directly to 0 during the first pass creates accidental extra zeroes.

Better Approach : TC: SC:

2 / 3

Algorithm: Store which rows and columns must become 0 in two helper arrays.

Pseudo:

Create row[m] and col[n] initialized with 0.
First pass: if matrix[i][j] == 0, set row[i] = 1 and col[j] = 1.
Second pass: if row[i] == 1 or col[j] == 1, set matrix[i][j] = 0.

Time: O(m*n)

Space: O(m+n)

Interview line: This is the cleanest version when the interviewer does not insist on constant extra space.

Optimal Approach : TC: SC:

3 / 3

Algorithm: Use the first row and first column of the matrix itself as marker storage.

Pseudo:

Keep a variable col0 = 1 to remember whether column 0 must become 0.
First pass: when matrix[i][j] == 0, mark matrix[i][0] = 0 and matrix[0][j] = 0.
If j == 0, set col0 = 0 because the first column also needs zeroing.
Second pass: iterate from bottom-right and zero matrix[i][j] when matrix[i][0] == 0 or matrix[0][j] == 0.
At the end of each row, if col0 == 0 then set matrix[i][0] = 0.

Time: O(m*n)

Space: O(1)

Key insight: row 0 and col 0 become free marker arrays, while col0 solves the matrix[0][0] collision.

PCode

1 / 3

FOR each row i
    FOR each column j
        IF matrix[i][j] == 0
            mark all non-zero cells in row i as -1
            mark all non-zero cells in column j as -1

FOR each row i
    FOR each column j
        IF matrix[i][j] == -1
            matrix[i][j] = 0

RETURN matrix

PCode

2 / 3

rows = number of rows
cols = number of columns
row[0...rows-1] = 0
col[0...cols-1] = 0

FOR each row i
    FOR each column j
        IF matrix[i][j] == 0
            row[i] = 1
            col[j] = 1

FOR each row i
    FOR each column j
        IF row[i] == 1 OR col[j] == 1
            matrix[i][j] = 0

RETURN matrix

2 / 2

01B/191

Set Matrix Zero

Continue

PCode

3 / 3

rows = number of rows
cols = number of columns
col0 = 1

FOR each row i
    FOR each column j
        IF matrix[i][j] == 0
            matrix[i][0] = 0
            IF j != 0
                matrix[0][j] = 0
            ELSE
                col0 = 0

FOR i from rows - 1 down to 0
    FOR j from cols - 1 down to 1
        IF matrix[i][0] == 0 OR matrix[0][j] == 0
            matrix[i][j] = 0
    IF col0 == 0
        matrix[i][0] = 0

RETURN matrix

1 / 1

02A/191

Pascal's Triangle

Problem Statement

Given an integer numRows, generate the first numRows of Pascal's Triangle. Each row starts and ends with 1, and every inner value is the sum of the two values directly above it. If the interviewer asks only for one row, mention the nCr based variant too.

Examples

Input: numRows = 5

Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Explanation: Every inner cell comes from previousRow[j - 1] + previousRow[j].

Input: numRows = 1

Output: [[1]]

Explanation: With one row, only the top of the triangle is returned.

Custom Notes

Boundary elements are always 1.
Full triangle generation is naturally O(n^2).
For a single row, nCr recurrence is the sharper answer.
Memory hook: row by row, two parents build one child.
Do not overuse factorials because they introduce overflow and repeated work.

Brute Force Approach : TC: SC:

1 / 3

Algorithm: Compute each value separately using combinations nCr.

Pseudo:

For every row i from 0 to numRows - 1:
For every column j from 0 to i, compute iCj.
Push the computed value into the current row.

Time: O(n^3) in a naive factorial or repeated multiplication style

Space: O(1) extra apart from answer

Why mention it: Good for showing mathematical understanding, but not the best construction approach.

Better Approach : TC: SC:

2 / 3

Algorithm: Build the triangle row by row using the previous row.

Pseudo:

Start with an empty answer.
For each row i, create an array of size i + 1 filled with 1.
For every inner index j from 1 to i - 1, set row[j] = ans[i - 1][j - 1] + ans[i - 1][j].
Push the row into the answer.

Time: O(n^2)

Space: O(n^2)

Interview line: This is the standard and most expected answer when the full triangle is required.

Optimal Approach : TC: SC:

3 / 3

Algorithm: For the full triangle, the row-by-row DP build is already optimal. For one specific row, use nCr recurrence.

Pseudo:

Full triangle case: use previous row to fill current row.
Single row case: start with 1 and iteratively derive the next combination value.
Push each derived value into the row answer.

Time: O(n^2) for full triangle, O(n) for one row

Space: O(n^2) for full triangle, O(1) extra for one row

Key insight: The problem has two common variants, and interviewers like when you mention both.

PCode

1 / 3

answer = empty list

FOR row from 0 to numRows - 1
    current = empty list
    FOR col from 0 to row
        value = nCr(row, col)
        append value to current
    append current to answer

RETURN answer

PCode

2 / 3

answer = empty list

FOR row from 0 to numRows - 1
    current = array of size row + 1 filled with 1
    FOR col from 1 to row - 1
        current[col] = answer[row - 1][col - 1] + answer[row - 1][col]
    append current to answer

RETURN answer

PCode

3 / 3

IF full triangle is required
    use row-by-row construction and return all rows

rowAnswer = [1]
current = 1

FOR col from 0 to rowIndex - 1
    current = current * (rowIndex - col) / (col + 1)
    append current to rowAnswer

RETURN rowAnswer

1 / 1

03A/191

Next Permutation

Problem Statement

Given an array representing a permutation, transform it into the next lexicographically greater permutation. If such a permutation does not exist, rearrange the numbers into the lowest possible order. The answer must be done in-place.

Examples

Input: nums = [1,2,3]

Output: [1,3,2]

Explanation: [1,3,2] is the smallest permutation larger than [1,2,3].

Input: nums = [3,2,1]

Output: [1,2,3]

Explanation: The sequence is already the largest, so we wrap to the smallest.

Custom Notes

Scan from the right to find the first dip.
Suffix to the right of the dip is always non-increasing.
Swap with the rightmost just-greater element.
Then reverse the suffix, do not sort it.
Memory hook: dip, swap, reverse.

Brute Force Approach : TC: SC:

1 / 3

Algorithm: Generate all permutations, sort them, and locate the next one.

Pseudo:

Generate every permutation of the array.
Sort all permutations lexicographically.
Find the current permutation and return the next one.

Time: O(n! * n)

Space: Huge

Why mention it: It explains the meaning of the task, but is never acceptable in interview implementation.

Better Approach : TC: SC:

2 / 3

Algorithm: Find the break point and sort the suffix after swapping.

Pseudo:

Find the first index i from the right where nums[i] < nums[i + 1].
Find the smallest number greater than nums[i] on the right.
Swap them.
Sort the suffix from i + 1 to end.

Time: O(n log n)

Space: O(1) extra if the sort is in-place

Interview line: This is acceptable logically, but the suffix is already in descending order, so reverse is enough.

Optimal Approach : TC: SC:

3 / 3

Algorithm: Use one backward scan for the dip, one backward scan for the swap target, then reverse the suffix.

Pseudo:

Find index i from the right such that nums[i] < nums[i + 1].
If no such i exists, reverse the whole array and return.
Find index j from the right such that nums[j] > nums[i].
Swap nums[i] and nums[j].
Reverse nums from i + 1 to end.

Time: O(n)

Space: O(1)

Key insight: Reverse works because the suffix is already in descending order before the final step.

PCode

1 / 3

allPermutations = generate all permutations of nums
sort allPermutations in lexicographic order

position = index of nums inside allPermutations

IF position is not the last index
    RETURN allPermutations[position + 1]

RETURN allPermutations[0]

PCode

2 / 3

i = rightmost index such that nums[i] < nums[i + 1]

IF i does not exist
    sort nums
    RETURN nums

find the smallest value on the right greater than nums[i]
swap it with nums[i]
sort nums from i + 1 to end

RETURN nums

PCode

3 / 3

i = rightmost index such that nums[i] < nums[i + 1]

IF i does not exist
    reverse whole array
    RETURN nums

j = rightmost index such that nums[j] > nums[i]
swap nums[i] and nums[j]
reverse nums from i + 1 to end

RETURN nums

1 / 1

04A/191

Maximum Subarray Sum

Problem Statement

Given an integer array nums, find the contiguous subarray that has the largest sum and return that sum. This is the classic Kadane problem. If asked, mention how to also recover the start and end indices of the best subarray.

Examples

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

Output: 6

Explanation: The subarray [4,-1,2,1] gives the maximum sum 6.

Input: nums = [1]

Output: 1

Explanation: A single element itself is the best subarray.

Custom Notes

Contiguous is the real keyword.
Negative running prefix hurts every future extension.
Initialize answer with nums[0], not 0, to handle all-negative arrays.
Memory hook: extend good prefix, drop bad prefix.
If the interviewer asks for the subarray, track tentative start and final boundaries.

Brute Force Approach : TC: SC:

1 / 3

Algorithm: Start every subarray and extend it to the right while tracking sum.

Pseudo:

For each start index i, set runningSum = 0.
For each end index j from i to n - 1, add nums[j] into runningSum.
Update the best answer with runningSum.

Time: O(n^2)

Space: O(1)

Why mention it: It is simple and still better than checking each subarray sum from scratch in O(n^3).

Better Approach : TC: SC:

2 / 3

Algorithm: Use DP thinking where best subarray ending at i is either nums[i] alone or nums[i] plus best ending at i - 1.

Pseudo:

Let dp[i] be the best subarray sum ending at i.
dp[i] = max(nums[i], nums[i] + dp[i - 1]).
Track the maximum value over all dp[i].

Time: O(n)

Space: O(n)

Interview line: This transitions directly into Kadane when you optimize away the DP array.

Optimal Approach : TC: SC:

3 / 3

Algorithm: Maintain currentSum for the best subarray ending here and bestSum for the global answer.

Pseudo:

Initialize currentSum = 0 and bestSum = nums[0].
For each number x, add x to currentSum.
Update bestSum = max(bestSum, currentSum).
If currentSum becomes negative, reset currentSum to 0.

Time: O(n)

Space: O(1)

Key insight: A negative prefix can only reduce the sum of any future subarray, so we drop it.

PCode

1 / 3

bestSum = negative infinity

FOR start from 0 to n - 1
    runningSum = 0
    FOR end from start to n - 1
        runningSum = runningSum + nums[end]
        bestSum = max(bestSum, runningSum)

RETURN bestSum

PCode

2 / 3

dp[0] = nums[0]
bestSum = dp[0]

FOR i from 1 to n - 1
    dp[i] = max(nums[i], nums[i] + dp[i - 1])
    bestSum = max(bestSum, dp[i])

RETURN bestSum

PCode

3 / 3

currentSum = 0
bestSum = nums[0]

FOR each value x in nums
    currentSum = currentSum + x
    bestSum = max(bestSum, currentSum)
    IF currentSum < 0
        currentSum = 0

RETURN bestSum

1 / 1

05A/191

Sort Colors

Problem Statement

Given an array nums containing only 0, 1, and 2, sort it in-place so that same colors are adjacent. Do not use the library sort for the intended interview solution. This is the Dutch National Flag problem.

Examples

Input: nums = [2,0,2,1,1,0]

Output: [0,0,1,1,2,2]

Explanation: All 0s move left, 1s stay in the middle, and 2s move right.

Input: nums = [2,0,1]

Output: [0,1,2]

Explanation: A single linear scan is enough with three pointers.

Custom Notes

low marks the next place for 0.
mid scans the unknown region.
high marks the next place for 2.
When swapping with high, do not increment mid yet.
Memory hook: left 0s, middle 1s, right 2s.

Brute Force Approach : TC: SC:

1 / 3

Algorithm: Use built-in sort or any comparison sort.

Pseudo:

Call sort(nums.begin(), nums.end()) or equivalent.

Time: O(n log n)

Space: Depends on sort implementation

Why mention it: It is correct but ignores the structure of the problem where values are only 0, 1, and 2.

Better Approach : TC: SC:

2 / 3

Algorithm: Count the number of 0s, 1s, and 2s, then overwrite the array.

Pseudo:

First pass: count zeros, ones, twos.
Second pass: fill the array with that many 0s, then 1s, then 2s.

Time: O(n)

Space: O(1)

Interview line: Easy and valid, but not the most elegant one-pass in-place partitioning answer.

Optimal Approach : TC: SC:

3 / 3

Algorithm: Maintain three pointers low, mid, and high.

Pseudo:

If nums[mid] == 0, swap nums[low] and nums[mid], then low++ and mid++.
If nums[mid] == 1, just mid++.
If nums[mid] == 2, swap nums[mid] and nums[high], then high-- only.
Continue while mid <= high.

Time: O(n)

Space: O(1)

Key insight: After swapping with high, the incoming value at mid is still unprocessed, so mid must stay.

PCode

1 / 3

sort nums using any standard comparison sort
RETURN nums

PCode

2 / 3

zeros = 0
ones = 0
twos = 0

FOR each value in nums
    increment zeros or ones or twos

rewrite nums with zeros copies of 0
then ones copies of 1
then twos copies of 2

RETURN nums

PCode

3 / 3

low = 0
mid = 0
high = n - 1

WHILE mid <= high
    IF nums[mid] == 0
        swap nums[low] and nums[mid]
        low = low + 1
        mid = mid + 1
    ELSE IF nums[mid] == 1
        mid = mid + 1
    ELSE
        swap nums[mid] and nums[high]
        high = high - 1

RETURN nums

1 / 1

06A/191

Best Time to Buy and Sell Stock

Problem Statement

You are given an array prices where prices[i] is the stock price on day i. Choose one day to buy and a later day to sell to maximize profit. If no profit is possible, return 0.

Examples

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

Output: 5

Explanation: Buy at 1 and sell at 6 for profit 5.

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

Output: 0

Explanation: Prices keep falling, so the best choice is no transaction.

Custom Notes

One transaction only.
Buy must happen before sell.
Profit today = today's price - minimum price seen earlier.
Memory hook: min so far, best profit so far.
Do not confuse this with the multiple-transactions stock problem.

Brute Force Approach : TC: SC:

1 / 3

Algorithm: Try every buy day with every later sell day.

Pseudo:

For each i, treat prices[i] as buy.
For each j > i, compute prices[j] - prices[i].
Track the maximum profit.

Time: O(n^2)

Space: O(1)

Why mention it: Straightforward baseline and makes the single-transaction constraint obvious.

Better Approach : TC: SC:

2 / 3

Algorithm: Precompute the best future sell price for each index and compare.

Pseudo:

Build a suffixMax array where suffixMax[i] is the maximum price from i to end.
For each day i, profit = suffixMax[i] - prices[i].
Track the maximum over all i.

Time: O(n)

Space: O(n)

Interview line: Good transition solution, but we can do the same in constant space.

Optimal Approach : TC: SC:

3 / 3

Algorithm: Maintain minPrice and update maxProfit while scanning once.

Pseudo:

Initialize minPrice = prices[0] and maxProfit = 0.
For each price, compute currentProfit = price - minPrice.
Update maxProfit with currentProfit.
Update minPrice = min(minPrice, price).

Time: O(n)

Space: O(1)

Key insight: The best buy for today is simply the minimum price that appeared before today.

PCode

1 / 3

bestProfit = 0

FOR buy from 0 to n - 1
    FOR sell from buy + 1 to n - 1
        profit = prices[sell] - prices[buy]
        bestProfit = max(bestProfit, profit)

RETURN bestProfit

PCode

2 / 3

suffixMax[n - 1] = prices[n - 1]

FOR i from n - 2 down to 0
    suffixMax[i] = max(prices[i], suffixMax[i + 1])

bestProfit = 0

FOR i from 0 to n - 1
    bestProfit = max(bestProfit, suffixMax[i] - prices[i])

RETURN bestProfit

PCode

3 / 3

minPrice = prices[0]
bestProfit = 0

FOR each price from left to right
    currentProfit = price - minPrice
    bestProfit = max(bestProfit, currentProfit)
    minPrice = min(minPrice, price)

RETURN bestProfit

1 / 1

07A/191

Rotate matrix by 90 degrees

Problem Statement

Examples

Custom Notes

Approach custom 1 : TC: SC:

1 / 1

FOR each row i FOR each column j IF matrix[i][j] == 0 mark all non-zero cells in row i as -1 mark all non-zero cells in column j as -1

FOR each row i FOR each column j IF matrix[i][j] == -1 matrix[i][j] = 0

RETURN matrix

PCode custom

1 / 1

FOR each row i
    FOR each column j
        IF matrix[i][j] == 0
            mark all non-zero cells in row i as -1
            mark all non-zero cells in column j as -1

FOR each row i
    FOR each column j
        IF matrix[i][j] == -1
            matrix[i][j] = 0

RETURN matrix