Let's crack Leetcode

Solving Leetcode, feeling dumb all of a sudden. No you're not dumb, it's just you don't know what method to use. Let's learn it together

Introduction

Ever thought of solving leetcode questions to crack interviews. But suddenly after 2-3 questions, you start feeling dumb, not knowing what even the question is saying. If yes, then you are at the correct place. Don't worry, you're not the only one, about a year ago, I too was in your shoes, and learnt that, once you know what methods to apply, you can smoothly drive through leetcode.

We shall follow the following guidelines, to keep this doc structured:

• Question number and title
• Topics Used (Leetcode Tags)
• Link to the question
• Meaning of the question
• Approach to solve it
• Python implementation

Now, we have all the things to dive into the leetcode ocean, so let's explore.

Question #36: Valid Sudoku

• Link to the question

Topics Used (Leetcode Tags)

• Array
• Hash Table
• Matrix

Meaning of the Question

Alright, here's the deal — we’re given a 9x9 Sudoku board, and we need to check if it’s valid. Not whether it can be solved, just if it follows all the classic Sudoku rules with what’s already filled in.

So the rules we need to follow are:

• Each row must have the digits 1 to 9 with no repeats.
• Each column must have the digits 1 to 9 with no repeats.
• Each of the nine 3x3 boxes (sub-grids) must also have digits 1 to 9 without repeats.

The board might have empty cells represented by ".", and we can ignore those — they don’t affect validity.

Example:
If there are two 5s in the same row, column, or 3x3 box — it's invalid.
If all filled numbers obey the rules, then the board is valid.

Hints to Solve It?

Here’s a good way to break it down:

• You’ll want to keep track of all the numbers you see for each row, column, and 3x3 box.
• A neat trick is to use a set to store each "seen" number along with its position context — like (row, num), (col, num), and (box, num).
• If you ever try to add a duplicate — boom, invalid board.

Try walking through a sample input manually first to see how these checks work before jumping to code.

Implementation

Python Code

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row_set = set()
        col_set = set()
 
        for r, row in enumerate(board):
            for c, val in enumerate(row):
                if val != '.':
                    if ((r, val) in row_set or
                        (c, val) in col_set or
                        ((r // 3, c // 3, val) in col_set)):
                        return False
                    row_set.add((r, val))
                    col_set.add((c, val))
                    col_set.add((r // 3, c // 3, val))
        return True

Question #38: Count and Say

• Link to the question

Topics Used (Leetcode Tags)

• Strings

Meaning of the question

The question says us to find the Run-Length Encoding of the string, defined by the following recursion rule:

• Recursive Case: countAndSay(n) returns the RLE of countAndSay(n-1)
• Base Case: countAndSay(1) returns $1$

A brief of RLE that it works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run).

Example: "224431" becomes "22241311" because 2 appears $2$ times, 4 appears $2$ times, 3 appears $1$ time and 1 appears $1$ time.

Hints to Solve It?

To solve this, let's brainstorm:

• The first idea to notice is how to define a recursive helper function to be called in countAndSay function, given the details.
  • Base Case is given
  • Recursive case is also given
• Second hint, the replacement is only for the consecutive positions. Given a number n, relate the digits with n[i] and n[i+1].
• Cracking the two gets you the answer

Implementation

Python Code

class Solution:
    def countAndSay(self, n):
        def helper(s, n):
            # `s` is the string of the RLE of the previous iteration
            # `n` is the number of times, the RLE has happened
            if n == 1: return s # Base case
 
            cnt = 0
            res = ''
 
            for i in range(len(s)):
                cnt += 1 # Increase the count of current digit
                if (i + 1 < len(s)) and (s[i] == s[i+1]):
                    continue
                if (i + 1 < len(s)) and (s[i] != s[i+1]):
                    res += f"{cnt}{s[i]}"
                    cnt = 0
                else:
                    res += f"{cnt}{s[i]}"
 
            return helper(res, n-1)
 
        return helper('1', n)

Question #2302: Count Subarrays With Score Less Than K

• Link to the question

Topics Used(Leetcode Tags)

• Array
• Binary Search
• Sliding Window
• Prefix Sum

Meaning of the question

Given an array nums and an integer k, we need to find contiguous(continous) sub-arrays such that their score $< k$.

Hints to Solve It?

• Can we make use of two-pointers since this is a continous sub-array problem?

• Given this array [2, 1, 4, 6, 2] and $k=10$, can you solve it roughly, using two pointers, say left and right?

  • First iteration

    [2, 1, 4, 6, 2]
     ^ ----- (lower)
     ^ ----- (upper)
    

    Slide upper such that it is before the first element that has $score \geq k$. So now the array looks like

    [2, 1, 4, 6, 2]
     ^ ----- (lower)
        ^ ----- (upper)
    

    Now there are $2$ arrays that satisfy the conditions, so we add right $-$ left $+1$ to our result variable.

    Now we move, the left and right both by $1$ step and update the sum variable accordingly.

  • Second iteration

    [2, 1, 4, 6, 2]
        ^ ----- (lower)
           ^ ----- (upper)
    

    Now again slide the upper such that it is before the first element that has $score \geq k$. So now the array looks like,

    [2, 1, 4, 6, 2]
        ^ ----- (lower)
        ^ ----- (upper)
    

    Now there is $1$ array that satisfy the conditions, so we add right $-$ left $+1$ to our result variable.

    Now we move, the left and right both by $1$ step and update the sum variable accordingly. And so on....

Implementation

Python Code

    def countSubarrays(self, nums: List[int], k: int) -> int:
        cnt = 0 # Result Variable
        total = 0 # Sum of current window
        left = 0 # The left pointer
 
        for right in range(len(nums)):
            total += nums[right]
 
            while total * (right - left + 1) >= k: # Score checking condition
                total -= nums[left]
                left += 1
 
            cnt += (right - left + 1) # Adding subarrays to the result variable
 
        return cnt

Question #2145: Count The Hidden Sequences

• Link to the question

Topics Used (Leetcode Tags)

• Array
• Prefix Sum

Meaning of the question

Given a differences array and an upper and lower bound, we need to find number of sequences, let it be called as unknown, that satisfies the following:

• $\text{difference[i]} = \text{unknown[i+1]} - \text{unknown[i]}$
• All elements of unknown are in the range: $[\text{lower}, \text{upper}]$

Hints to Solve It?

Before you see the implementation, give this a thought.

• To fit unknown in the range: $[\text{lower}, \text{upper}]$, what elements can we put the constraint on? Do we need to talk about mean, median, max, min, etc.?
  • Let's say I want to fit a sequence, between $[5,10]$, then I'll constrain the maximum and minimum elements of sequence to $[5,10]$ and my sequence is settled
• Does the range or $\max(\text{unknown})-\min(\text{unknown})$ depend on the elements of the list unknown?
• Now can I find the $\max(\text{unknown})-\min(\text{unknown})$, using the differences array, given the first element is $x$
• If you graph the unknown letting the first element be $x$, and draw bounds, you see that the answer is $(\text{upper} - \text{lower}) - (\max - \min) + 1$.
  • If the value is $\leq 0$, there is no such sequence

Implementation

Python Code

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
 
        # Maintain the max and min elements
        max_elem, min_elem = 0, 0
        # Let the initial element be 0
        prev = 0
 
        # Loop through `differences`
        for i in differences:
            curr = prev + i # Find the current element
            # Update `min` and `max` elements
            if curr > max_elem: max_elem = curr
            elif curr < min_elem: min_elem = curr
            # Move `curr` to `prev`
            prev = curr
 
        res = (upper - lower + 1) - (max_elem - min_elem)
        return res if res > 0 else 0

Question #2785: Sort Vowels in a String

• Link to the question

Topics Used(Leetcode Tags)

• String
• Sorting

Meaning of the question

We are given a string str. We need to return another string, let's say t that uses the input string str based on the following rules.

• Rule 1: All vowels in the string str must be sorted and placed at the same indexes where the vowels are present in str. That means the vowels need to be swapped based on their ASCII codes sorted in ascending order.
• Rule 2: All other characters other than the vowels must remain as it is.

Hints to Solve It?

Think about this questions:

• What data structure can be edited based on indexes?
• Do consonants require any operations, like swapping?
• The vowels should be swapped but one vowel should take the place of another vowel from the same string.
• What data structure allows $O(1)$ finding of element to check whether a given character is a vowel or not?

Implementation

Python Code

class Solution:
    def sortVowels(self, s: str) -> str:
        t = [""] * len(s)
        vowels = ""
        known_vowels = set("aeiouAEIOU")
        pos = []
 
        for idx, i in enumerate(s):
            if i not in known_vowels:
                t[idx] = i
            else:
                vowels += i
                pos.append(idx)
 
        vowels = sorted(vowels)
        for idx, x in enumerate(pos):
            t[x] = vowels[idx]
 
        # print(vowels, pos, "".join(t))
        return "".join(t)

Question #3021: Alice and Bob Playing Flower Game

• Link to the question

Topics Used (Leetcode Tags)

• Math

Meaning of the question

The question here first off sets the background for us which is the flower gams.

There are two players, Alice and Bob. The game they are playing has 2 lanes, the first lane has let's say $x$ flowers and the second lane has $y$ flowers. Now, both the players choose a direction, clockwise or counterclockwise, and they can't be same. The rules are as follows:

• Alice starts the game.
• Alice picks the first flower, in the direction she chose. Then Bob and so on.
• The player who chose the last flower in its direction wins.

Now, the question tells us that the first lane can have $[1, n]$ flowers and second lane can have $[1, m]$. Given $m$ and $n$, we now need to find the number of possible outcomes where Alice wins the game.

Hints to Solve It?

Before you see the implementation, try to work out the smaller cases like $m=1, n=2$, $m=2, n=3$, and so on.

Since the topic used is Math, can you find any general formula that can help you in this problem?

Implementation

Python Code

class Solution:
    def flowerGame(self, n: int, m: int) -> int:
       return n*m//2

Signing Off

That's it from this article, I'll try to add more and more questions to this article. I'll also post a github repo link below, that contains all the code discussed. Do star that, if you find this helpful. This is your guy Harsh, signing off. See you in the next article.

Github Repo

• Link: Github Repo

Subscribe to Our Newsletter