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 #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   

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: https://github.com/harshshah-codes/leetcode-solutions

Subscribe to Our Newsletter