1672 - Richest Customer Wealth

Let’s imagine you're standing in a busy bank lobby. Each customer has multiple accounts — savings, checking, maybe even a hidden investment tab. Your task? Simple: figure out which customer has the most total money across all their accounts.

That’s exactly what this problem wants you to do.

You’re given a grid called accounts.

• Each row represents a customer.
• Each column in that row represents the amount of money they have in a particular bank account.

Your mission:

👉 Add up each customer’s total wealth,

👉 Compare all totals,

👉 And return the maximum.

It’s simple, clean, and a perfect warm-up problem for beginners in Python and DSA.

🧠 How to Think About the Problem

Picture the grid like this:

For each customer:

1. Add everything in their list (their accounts).
2. Keep track of the highest sum you’ve seen.

That’s it — you're basically running a mini "richest person contest."

Example 1

Input :

accounts = [[1, 2, 3],  
            [3, 2, 1]]

Step-by-step:

• Customer 1 → 1 + 2 + 3 = 6
• Customer 2 → 3 + 2 + 1 = 6

Both end up with 6, so the richest wealth is 6.

Output: 6

Example 2

Input :

accounts = [[1, 5],  
            [7, 3],  
            [3, 5]]

Step-by-step:

• Customer 1 → 6
• Customer 2 → 10
• Customer 3 → 8

The richest customer is the second one with 10.

Output: 6

🧩 Constraints

• You will always have at least 1 customer and 1 account.
• Up to 50 customers and 50 accounts each.
• Each amount of money is between 1 and 100.

So everything fits neatly — no crazy edge cases to fear.

🐍 Python Solution

Here’s a simple Python function you can run:

def maximum_wealth(accounts):
    richest = 0
    
    for customer in accounts:
        wealth = sum(customer)       # total money this customer has
        richest = max(richest, wealth)
    
    return richest

If you like doing things in a single line, Python even lets you do this:

def maximum_wealth(accounts):
    return max(sum(customer) for customer in accounts)

1 - Two Sum

Let’s set the scene.

You’re wandering through a list of numbers — imagine them laid out like cards on a table. Somewhere among them are two special numbers that add up exactly to a target value you’ve been given. Your mission?

👉 Find their positions in the array.

Not the numbers themselves — the indices where they live.

This is the famous Two Sum problem, one of the most common warm-up problems in coding interviews — simple, elegant, and the perfect way to start building your DSA muscle.

🎯 The Task

You’re given:

• An array nums
• A number target

Your goal is to find two different elements in nums that add up to target.

You can’t:

• Reuse the same element twice
• Return more than one answer (the problem guarantees exactly one solution)

You can:

• Return the indices in any order. [i, j] or [j, i] — totally fine.

Example 1

Input :

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

Imagine walking through the list:

• Look at 2 → you need 7 to make 9.
• Hey, 7 is right there next to it!

So we return :

Output: [0, 1]

Because nums[0] + nums[1] = 9.

Example 2

Input:

nums = [3, 3], target = 6

Two 3s right next to each other. Perfect.

Output: [0, 1]

🧩 Constraints

• You’ll always have at least 2 numbers.
• The array can go up to 10,000 elements.
• Numbers and targets can be large, positive or negative.
• You’re guaranteed exactly one valid pair.

No trick cases, no ambiguity — clean and predictable.

🧠 Thinking About the Follow-Up

The brute-force way? Check every pair — that’s O(n²) time.

But can we do better? Absolutely.

The trick lies in using a hash map (Python’s dictionary) to remember which numbers you’ve already seen and where.

🐍 Python Solution

Here’s the standard, interview-ready solution using a dictionary:

def twoSum(self, nums: List[int], target: int) -> List[int]: # type: ignore
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i

Why this works fast:

• You look at each number only once → O(n)
• Dictionary lookups are near-instant
• You track complements as you go

This is exactly what interviewers love to see — simple, clean, and efficient.

1351 - Count Negative Numbers in a Sorted Matrix

Imagine you're exploring a snowy mountain represented as a grid. Each row slopes downward, and each column slopes downward too — meaning the numbers are sorted in non-increasing order both left-to-right and top-to-bottom.

At the top-left of this “mountain,” everything is calm and positive. But as you move right or down, the temperature drops… eventually going into the negative zone ❄️.

Your mission? 👉 Find how many negative numbers are hiding in this chilly matrix.

Let’s walk through it together.

🧊 Understanding the Matrix

You're given a matrix like this:

[
  [4, 3, 2, -1],
  [3, 2, 1, -1],
  [1, 1, -1, -2],
  [-1, -1, -2, -3]
]

Because the matrix is sorted in non-increasing order:

• Each row goes from big → small
• Each column goes from big → small

So once you hit a negative number in a row, everything to its right is also negative. Same goes downward.

This is an amazing property — and we'll use it to our advantage later.

🧪 Example 1

Input:

grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

Let’s count them:

• Row 1 → 1 negative
• Row 2 → 1 negative
• Row 3 → 2 negatives
• Row 4 → 4 negatives
• Add them up → 8

Output: 8

🧪 Example 2

Input:

grid = [[3, 2], [1, 0]]

Everything here is non-negative — no winter storms yet.

Output: 0

Constraints

• Up to 100 x 100 grid
• Numbers range from – 100 to 100
• Always properly sorted
• Always rectangular

Nothing scary — very manageable.

⏳ Basic Approach (Simple but Slower)

The most straightforward way? Walk through every cell and count negatives.

But that takes O(m × n) time — okay, but not optimal.

⚡ Follow-Up Challenge: Can You Do Better?

Yes! Thanks to the matrix’s sorted structure, you can find the answer in O(m + n) time using a clever trick.

🧭 The Staircase Walk (Efficient Approach)

Start at the bottom-left corner. From here:

• If the number is negative → everything to its right is also negative → count them and move up
• If the number is non-negative → move right to find negatives

This way, you never revisit cells — giving you the faster O(m + n) solution.

🐍 Python Code (O(m + n) Solution)

def count_negatives(grid):
    rows = len(grid)
    cols = len(grid[0])
    
    r = rows - 1      # start at bottom-left
    c = 0
    count = 0
    
    while r >= 0 and c < cols:
        if grid[r][c] < 0:
            # all elements to the right are negative
            count += (cols - c)
            r -= 1  # move up
        else:
            c += 1  # move right
    
    return count

31 - Next Permutation

Imagine you have a small set of number tiles laid out in a row — like [1, 2, 3]. Now imagine that every time you reorder these tiles in a different way, you get a new permutation.

If you listed all these permutations in sorted order, you’d get a big list like:

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

Now here's the fun part: Your task in this problem is not to generate all permutations. Instead, you simply need to find the next one — the permutation that comes immediately after the current arrangement.

Think of it like flipping to the next page of a book… except the book is made of numbers.

What “Next Permutation” Really Means

The next permutation is the next lexicographically greater arrangement of the same list of numbers.

• If such a next arrangement exists → return it.
• If the current arrangement is already the highest possible order → wrap around and return the smallest (ascending) order.

This is like hitting “next” on a looped playlist — when you’re at the final song, it jumps back to the first.

🧪 Example 1

Input: [1, 2, 3]

Output: [1, 3, 2]

🧪 Example 2

Input:

[3, 2, 1]

This is the largest possible ordering. No greater permutation exists.

So we flip to the smallest:

Output: [1, 2, 3]

How to Think About It

Imagine walking through the array from right to left, looking for the first spot where the order breaks — the first place where a number is smaller than the one after it.

Why? Because that’s the place where you can “bump up” the number and create a slightly bigger permutation.

Here’s the high-level plan:

Step 1 — Find the “dip”

Starting from the right, find the first nums[i] < nums[i + 1]. This index i is where things can be improved.

If no such index exists → the array is fully descending → return ascending order.

Step 2 — Find the next bigger number on the right

In the tail of the array (to the right of i), find the smallest number that is greater than nums[i], and swap them.

This is like upgrading the number just enough.

Step 3 — Reverse the right side

Everything to the right of i was previously in descending order (largest to smallest). To get the smallest next permutation, flip it into ascending order.

This ensures the answer is the next permutation — not a giant leap forward.

🐍 Python Code (In-Place)

def next_permutation(nums):
    n = len(nums)
    i = n - 2

    # Step 1: Find the first decreasing element from the right
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # Step 2: Find the next larger element on the right
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]

    # Step 3: Reverse the right portion
    nums[i + 1:] = reversed(nums[i + 1:])