coding interview preparation

Regular Expression Matching Using Dynamic Programming

Posted on July 26, 2021July 26, 2021 by Swetha Kannan

This is a follow up on the previous post where we solved Regular Expression Matching using simple recursion. In this post we will solve the same problem using Dynamic Programming. Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems where the optimal solution to the problem is obtained by solving for optimal solutions to the subproblems.

Problem Statement

Given an input string and a regex pattern, implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ matches any single character
‘*’ matches zero or more of the preceding element (the char before *)

Examples

s = ‘aa’, p = ‘ab’ Not a match
s= ‘bbbbb’, p = ‘b*’ Match because ‘*’ matches zero or more of the preceding element b
s= ‘fljflf’, p = ‘.*’ Match because we want to match zero or more of the preceding element which is any character in this case
s = ‘oop’, p = ‘r*o*p’ Match because r is present 0 times, o is present twice and p is a direct match

Thought Process

In any dynamic programming problem we should first define the subproblem. Let’s consider an example where s = ‘bbbbb’ and p = ‘b*b*c*’. If we use the recursive solution to solve the problem, the recursion tree will branch out as shown below. Although not all the branches are represented in the diagram, we can clearly see that some of the subproblems are repeatedly solved over and over again and this is an expensive computation. One way to avoid solving repeated problems is to remember the results of a computation using a technique called Memoization.

Each subproblem call will resemble isRegexMatch(s[i:], pattern[j:]) where i and j are indexes used to slice the string and the pattern respectively. So we do not have to memoize the entire substring and substring of the pattern. So instead of

mem[(s[i:], pattern[j:])) = result

We will use only i and j to index the result in mem such as

mem[(i, j)] = result

We will therefore use the exact same solution from our previous solution except this time we will store the results for future lookup.

Complexity

For a string of length S and pattern of length P, we call dp(i, j) at the worst case for all the possible subproblems for i = 0 to S and j = 0 to P. So the time complexity will be O(SP).

Same for space complexity since we are caching the results of the subproblems O(SP).

Solution

def isRegexMatch(s, pattern):

    mem = {}
        
    def dp(i, j):
        if (i, j) not in mem:
            if j == len(pattern): # Check if pattern is empty, if so string s should also be empty
                mem[(i,j)] = i == len(s)
            else:
                # Check the first character match in s and pattern
                # String should not be empty
                # The first characters exactly match (Or)
                # pattern's first char contains "." to match any char in s
                is_first_char_match = len(s) > i and (s[i] == pattern[j] or pattern[j] == ".")
                
                # When '*' is present in the second char of pattern    
                if j < len(pattern) - 1 and pattern[j+1] == "*":
                    mem[(i,j)] = dp(i, j+2) or (is_first_char_match and dp(i+1, j))
                else: 
                    # Continue checking the remaining characters using recursion
                    mem[(i,j)] = is_first_char_match and dp(i+1, j+1) 
                
        return mem[(i,j)]
    return dp(0, 0)

Hope you enjoyed solving this dynamic programming example using Memoization technique. See you in the next post!

Arrays and Strings, Data Structures/ Leetcode, Recursion

Regular Expression Matching

Posted on July 14, 2021 by Swetha Kannan

Given an input string and a regex pattern, implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ matches any single character
‘*’ matches zero or more of the preceding element (the char before *)

Examples

s = ‘aa’, p = ‘ab’ Not a match
s= ‘bbbbb’, p = ‘b*’ Match because ‘*’ matches zero or more of the preceding element b
s= ‘fljflf’, p = ‘.*’ Match because we want to match zero or more of the preceding element which is any character in this case
s = ‘oop’, p = ‘r*o*p’ Match because r is present 0 times, o is present twice and p is a direct match

Thought Process

Let’s approach this problem step by step.

Case 1: The simplest case would be when the given string and the pattern do not contain any ‘.’ or ‘*’ characters but only alphabets.

s = 'aa' and p = 'ab'

In this case we would check the string and the pattern from left to right to see if each character in the string matches the characters in the pattern.

a = a matched so far

b != a Match failed so return False

Case 2: When no ‘*’ characters are present but only ‘.’. In this case ‘.’ can match any single character. So we check for that condition and continue to check the remaining characters in the given string and the pattern using recursion.

def isRegexMatch(s, pattern):
    # If pattern is empty, as long as string is also empty => true
    # If pattern is empty but string is not empty => return false
    if not pattern:
        return not s

    # Check the first character match in s and pattern
    # String should not be empty
    # The first characters exactly match (Or)
    # pattern's first char contains "." to match any char in s
    is_first_char_match = len(s) > 0 and (s[0] == pattern[0] or pattern[0] == ".")
    
    # Continue checking the remaining characters using recursion
    return is_first_char_match and isRegexMatch(s[1:], pattern[1:])

Case 3: When the regex pattern contains both ‘.’ and ‘*’ characters, things get a little complicated.

Note that the pattern will never begin with ‘*’ because it denotes that a preceding character can be present 0 or more times. So it will ALWAYS be present only as the second character when that part of the pattern is being processed after a recursive call, For example: a*, .*

So we can have a condition that evaluates this logic as shown below.

if len(pattern) >= 2 and pattern[1] == "*"

If the above condition holds true, then we check regex match differently due to the presence of ‘*’. Let’s think about how we can do that. There are two valid scenarios that are allowed here.

Scenario 1: s = "aaaa", pattern = "c*a*"

In this case len(pattern) = 4 which is >= 2 and pattern[1] = ‘*‘. We see that c is not present in the string s but it can occur zero 0 or more times. In this case we can ignore checking the first two characters of the pattern and continue the recursion as shown below.

isRegexMatch(s, pattern[2:]) => isRegexMatch("aaaa", "a*")

Scenario 2: s = "aaaa", pattern = "a*"

In this case len(pattern) = 2 which is >= 2 and pattern[1] = ‘*‘. s contains ‘a’ which is a direct match with the first character in the pattern. So we check for first character match and continue recursion on the rest of the string.

is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("aaa", "a*")

Note that we pass the full pattern string to the recursion call here because ‘*’ can match zero or more characters of ‘a’. So we want to check the string for that as well. The following recursive calls will hold true.

isRegexMatch("aaa", "a*") =>
is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("aa", "a*")

isRegexMatch("aa", "a*") =>
is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("a", "a*")

isRegexMatch("a", "a*") =>
is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("", "a*")

isRegexMatch("", "a*") =>
isRegexMatch(s, pattern[2:]) => isRegexMatch("", "") so final result will be true.

if len(pattern) >= 2 and pattern[1] == "*":
    return isRegexMatch(s, pattern[2:]) or (is_first_char_match and isRegexMatch(s[1:], pattern))

Complexity

For a given string of length S and pattern P, we make recursive calls using indexes s[i:] and pattern[2j:] (When ‘*’ is present). The recursive tree can go to a depth of (S+P/2) which will have 2^h leaf nodes where h = (S+P/2), so 2^(S+P/2) leaf nodes. This means the recursion will branch into 2^(S+P/2) sub-problems.

If we pass the entire string and pattern at the worst case, the complexity of solving a sub-problem will be O(S+P). So the time complexity will roughly be

O((S+P) * 2^(S+P/2))

To read more about the complexity calculation for this problem, here’s a detailed article.

Putting it all together.

Solution

def isRegexMatch(s, pattern):
    # If pattern is empty, as long as string is also empty => true
    # If pattern is empty but string is not empty => return false
    if not pattern:
        return not s

    # Check the first character match in s and pattern
    # String should not be empty
    # The first characters exactly match (Or)
    # pattern's first char contains "." to match any char in s
    is_first_char_match = len(s) > 0 and (s[0] == pattern[0] or pattern[0] == ".")
    
    # When '*' is present in the second char of pattern
    if len(pattern) >= 2 and pattern[1] == "*":
        return isRegexMatch(s, pattern[2:]) or (is_first_char_match and isRegexMatch(s[1:], pattern))

    else:
        # Continue checking the remaining characters using recursion
        return is_first_char_match and isRegexMatch(s[1:], pattern[1:])

Hope you enjoyed solving the regular expression problem. In the next post, we will look at how to improve upon this solution using Dynamic Programming!

Arrays and Strings, Data Structures/ Leetcode, Palindromes

Longest Palindromic Substring

Posted on June 7, 2021June 7, 2021 by Swetha Kannan

Problem Statement

Given a string s, we have to return the longest palindromic substring.

Note: Palindromes are words or phrases that read the same backward and forward, letter for letter, number for number, or word for word. Source: Grammarly

Examples

Input: s = “babad”

Output: “bab”

Input: s = “dfgggggkl”

Output: “ggggg”

Input s = “a”

Output: “a”

Thought Process

In any given string, to find the longest palindromic substring, the brute force approach would be to consider every possible substring and then have a helper function to check if it is a palindrome. This results in a cubic complexity for a string of length N. Why O(N³) complexity? To check if a string is a palindrome or not, we will have to traverse through the whole substring. At the worst case, this will be the entire string s. This takes O(N). We will then have to use two for loops to check each possible substring which will be O(N²). Now let’s think of an efficient way of doing this.

There are two types of palindromes.

Palindromes with an even number of letters. Examples: “aa”, “abba”, “cdeedc”
Palindromes with an odd number of letters. Examples: “a”, “aba”, “cdedc”

The speciality of palindromes is that they expand from a central point and mirror each other on the left and right. How to define what is the center? In an even length palindrome, the center is in between two letters. In “abba”, the center is in between the two “b”s. In “aba”, which is an odd length palindrome, the center is “b”.

How many possible centers are there in a given palindrome?

Example 1: “aba”

The possible centers to consider are a, a <-> b, b, b <-> a, a ie., 5 centers

Example 2: “abba”

The possible centers are a, a <-> b, b, b <-> b, b, b <-> a, a ie., 7 centers

For N = 2, possible centers = 3

For N = 3, possible centers = 5

For N = 4, possible centers = 7

For N = 5, possible centers = 9

Let’s look at the possible centers and see by how much does it go up for each value of N.

(5 – 3) = (7 – 5) = (9 – 7) = 2

We can calculate the number sequence by using xn. In this case x = 2, so 2N. We notice that for N = 3, the possible centers are not 2N = 6, we have to subtract 1. So the generalized sequence will be 2N – 1.

To solve the given problem, we can iterate through each character in the string while considering it as a possible center for a palindrome. We can then expand around this center while checking its left and right side for mirroring. Since there can be odd length and even length palindromes, we have to consider the max length between them.

To get the max odd palindrome, we pass the left and right pointers as the current character since the center is a single character. Example: “aba”, when i = 1 (b), the left and right starting points to expand around will both be “b”, i = 1.

To get the max even palindrome, we pass the left and right pointers as the current and next character since the center is in between two characters. Example: “abba”, when i = 1 (b), the left and right starting points to expand around will be “b”, i = 1 and the next “b”, i = 2.

We can then take the string with the max length between these two values.

longest_palindromic_substring = ""

for i in range(len(s)):
    odd_max = check_palindrome(s, i, i)
    even_max = check_palindrome(s, i, i+1)

    longest_palindromic_substring = max(longest_palindromic_substring, odd_max, even_max, key = len)

Now let’s write a helper function to check if the given string is a palindrome.

def check_palindrome(s, left, right):

    while left >= 0 and right < len(s):

        if s[left] == s[right]: # check mirroring
            left -= 1
            right += 1
        else:  # Break the loop if the characters mismatch
            break  

    return s[left+1: right]

Complexity

O(N²) time – O(N) to expand around each center and O(N) to check if the substring is a palindrome

O(1) space

Putting it all together.

Solution

def find_longest_palindromic_substring:
    
    if not s:
        return s
    
    def check_palindrome(s, left, right):

        while left >= 0 and right < len(s):

            if s[left] == s[right]: # check mirroring
                left -= 1
                right += 1
            else:  # Break the loop if the characters mismatch
                break  

        return s[left+1: right]

    longest_palindromic_substring = ""

    for i in range(len(s)):
        odd_max = check_palindrome(s, i, i)
        even_max = check_palindrome(s, i, i+1)

       longest_palindromic_substring = max(longest_palindromic_substring, odd_max, even_max, key = len) # This will return the max value based on string length (key = len)

    return longest_palindromic_substring

Hope you enjoyed this step by step problem solving approach for the longest palindromic substring problem and learnt a thing or two about palindromes!

Arrays and Strings, Data Structures/ Leetcode, Sliding Window Technique

Longest Substring Without Repeating Characters

Posted on June 1, 2021 by Swetha Kannan

Problem Statement

In a string s, find the length of the longest substring without repeating characters.

Example

Input: s = “abcabcbb”
Output: 3 (“abc”)

Note: Substring means that the letters in the string should be continuous.

Thought Process

The brute force approach to this problem is to construct every possible substring from the given string and keep track of the longest seen substring so far without any repeating characters. This is highly inefficient.

Whenever we want to optimize array or string problems which have some kind of order in them, in this case the continuity of a substring, it’s good to pause and consider whether we can apply the two pointer technique or the sliding window approach. Think about using two pointers in the following situations.

Using two pointers starting at the beginning and end of the array to shrink our search space while comparing the specific elements at start and end pointers
Two pointers starting at the beginning of the array and one moving at a faster speed than the other

Think of sliding window approach in the following situation.

This technique can be used when we need to solve contiguous subarray/ substring problems to solve the overall problem. The window size may be fixed or variable. The window size is variable when we need to find the subarray or the substring in the given problem that meets a certain criteria which is the scenario in this current problem.

Let’s use two pointers called start and end to shrink and expand our sliding window accordingly.

Expand the window when there are no repeated characters in the sliding window
Shrink it when we see a repeated character

Now that we are certain about how we will be using the pointers, the next step is to think about how to formulate shrinking and expansion.

How do we keep track of characters already seen?

As we expand our sliding window considering each additional character added to the substring, let’s store a mapping of a character and the last index where it was seen in a hash map.

lastSeenIndexes = {a: 0, b: 1} etc.

To expand:

We can use the end pointer to traverse the string from left to right for every iteration from i = 0 to i = n-1.

To shrink:

Shrinking the sliding window means determining the position of the start pointer.

The start pointer may have already advanced past the last repeated character
Or we need to move it to the index right after the index of the last seen character

start = max(start, lastSeenIndexes[c] + 1)

Complexity

O(N) time complexity and O(N) space

Solution

def lengthOfLongestSubstring(self, s):
     """
     :type s: str
     :rtype: int
     """
     if not s:
        return 0
        
     start, maxLen = 0, 0
     lastSeenIndexes = {}
        
     for end in range(len(s)):
         c = s[end]
            
         if c in lastSeenIndexes:
             start = max(start, lastSeenIndexes[c] + 1)
                
         lastSeenIndexes[c] = end
            
         maxLen = max(maxLen, end - start + 1)
            
    return maxLen

Hope you enjoyed this step by step problem solving approach for the longest substring without any repeating characters problem!

Arrays and Strings, Data Structures/ Leetcode, Two Pointer Technique

[Problem Solving] Three Sum – Using Two Sum

Posted on May 12, 2021 by Swetha Kannan

To understand the following problem, we will be using what we learnt in the two sum problem. If you haven’t read it yet, do make sure to understand it before proceeding. Here’s the link.

Problem Statement

We have an array of integers called nums. We need to return three numbers let’s call it nums[i] = x, nums[j] = y and nums[k] = z that add up to 0. The indices of the returned numbers should all be unique ie., i != j != k

Assumptions

Solution set should not contain duplicate triplets
Empty array results in an empty set
If there are less than three numbers in the input array, return an empty set

Examples

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

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

Thought process

The brute force way to do this would be to loop using three for loops to search for three numbers in the array that sum up to 0. But this would have an O(n³) time complexity. So we need to be slightly better than that. The next best in time is an O(n²) solution. Remember that we should not return duplicate indices.

Let’s say nums[i] + nums[j] + nums[k] = 0

Then nums[i] + nums[j] = – nums[k]

This now resembles a two sum problem where we need to look for nums[i] and nums[j] such that they add up to a target = – nums[k]

To condense the problem, what we can do is loop through the array from k = 0 to k = n-1 and for every nums[k], find two numbers nums[i] and nums[j] that add up to a target = – nums[k].

How can we avoid adding duplicate triplets to the results list? A naive solution is to add all the duplicates to the result list and in the end return the set(result) to remove duplicates. This way we still do unnecessary work on finding the same two numbers that add up to a target value -nums[k].

To avoid executing a two sum loop on duplicates, let’s reuse our solution from the two sum problem where the input array was sorted and contained duplicates. We can sort the nums list and skip searching for two sum values whenever the current nums[k] = nums[k-1]. Sorting makes it easier to club duplicate values together. For ex:

Input: [-1,0,1,2,-1,-4]

Sorted List: [-4, -1, -1, 0 ,1,2]

One of the solutions here that adds up to 0 will be [-1, 0,1]. Now if we did not skip for target = nums[2] = -1, we will again get a solution set of [-1, 0, 1] in the result.

Complexity

O(N²) time complexity and O(1) extra space

Solution

def three_sum(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    # Edge case when the array is empty
    if not nums:
       return []
    
    n = len(nums)
    # Another edge case when the input array does not have 3 elements
    if len(nums) < 3:
       return []
        
    results = []

    # Sorting helps to club duplicate values together
    nums.sort()
        
    for k in range(0, n):
        # If the current num is equal to the previous value, then skip execution because we will be getting a duplicate solution set
        if k > 0 and nums[k] == nums[k-1]:
            continue
                
            target = -1 * nums[k]
            start = k + 1
            end = n - 1
            
            two_sum(nums, target, results, start, end)
    return results

# Same as the two sum solution that we coded in the previous article
def two_sum(nums, target, results, s, e): 

    while s < e:
            
        if nums[s] + nums[e] == target:
            results.append([nums[s], nums[e], -target])
            s += 1 # Advance the starting pointer to continue to look for other solutions

            # Skip duplicate solutions in two sum
            while s < e and nums[s] == nums[s-1]:
                s += 1
            
        elif nums[s] + nums[e] < target:
           s += 1
        else:
           e -= 1

coding interview preparation, Professional Improvement

The different types of interviewers whom you may have to work with.

Posted on July 13, 2020July 13, 2020 by Swetha Kannan

The future co-worker

This is an interviewer who can put themselves in your shoes the minute they walk-in. They understand what an important day this is for you and the nervousness you carry. They know that you have done incredible amounts of hard work and won’t try to belittle you in any way. They are here because they want to solve the problem with you. As you go through your interview, whether you aced it or not, you will come out of it feeling like you had a good conversation where you learnt something. This is the kind of interviewer who is great to work with during and after the interview. Although you might think that you are the only one being evaluated, it is a great opportunity for you to evaluate whether you can see yourself working with this person in the future.

Now that we’ve gotten the best package, let’s look at some of the not-so-good scenarios that can happen.

The one who wouldn’t look at you

Sometimes interviewers have been told to type every little conversation that goes on in the room. Although there are some great note-takers who aren’t constantly distracted, most of them in this category don’t care to look at you much. The typing is distracting, there is no eye contact, mostly they aren’t listening nor trying to have an organic conversation with you.

If you had to interview with someone like that, don’t be afraid to take up space in the room. If you start feeling stressed or the interview feels too cold, politely let them know that the typing is a little distracting to your thought process. You can also pause a few times and wait to get their attention before proceeding so that they don’t miss out on the key points that you are mentioning during your interview. It is important for you to stay assured that you are not responsible for their distracted state no matter how boring the question is, so go about it confidently because this day is more important to you than it is for them.

The one who wants you to be a mind-reader

Some interviewers do not let you solve a problem using your own methods. This could be because they aren’t aware of more than one way of solving a problem or they aren’t able to understand how you’re trying to solve it.

Let us always assume the latter because if you are standing there judging the interviewer for not knowing multiple ways of solving a problem, it won’t benefit you in any way. This can create a communication barrier between the both of you. This is when you can take a step back and try to best explain your algorithm with a few examples. Place emphasis on why your approach might work. Pay attention when the interviewer counters it. In some cases, they might expect you to go for the most efficient solution right away. You have probably only come up with a brute force one and can’t really think of how it can be improved. When you feel stuck in this state, explain that you haven’t quite gotten there but you are hoping to get started with a basic solution and iteratively improve upon it once you see the caveats. Most interviewers will be fine with this approach.

The one with the unnecessary arrogance

An interviewer’s job is to make a case for someone who exhibits potential to be a good developer and fit for the company and its culture. Unfortunately, some of them try to check if you are as smart as them, or pick a super difficult problem. This might mostly be a junior developer whose idea of Software Development hasn’t grown beyond solving difficult Leetcode questions yet.

Such an interview scenario can be extremely stressful and the worst outcome is you experiencing a mental block. Try to pick a few easy example cases and manually solve the problem. See if you can turn that into a brute force algorithm that can work for the most common cases. You can then discuss edge cases and improve your algorithm. At any point, an interviewer should not try to trick you or turn it into a stress interview. If that starts to happen, take a few deep breaths and start over. Remember that it’s okay to sometimes not solve it at all. There are thousands of different problems out there and it’s completely okay to be clueless when an overly difficult problem gets presented to you. It was just one of those unlucky days.

The silence of the lambs

This type of interviewer can make you feel nervous throughout the interview by being silent. You may feel stuck at various points on whether your approach is right, waiting for cues to proceed or step back. A good interviewer will make sure to guide you and let you know when you are going in the wrong direction, but sometimes they might not. If this happens, calm yourselves and give it your best shot. Start explaining how you plan on solving the problem and once you are done, stop and explicitly ask whether you can go ahead and code it up. Get to this point as quickly as possible so that you have enough time to brainstorm an alternate approach if your first one doesn’t work out. Be aware of time and allocate a comfortable chunk of time to code the solution.

Hope this post helped you to mentally prepare yourselves to interview with any type of interviewer whom you might encounter. Good luck with your upcoming interviews 🙂

Arrays and Strings, Data Structures/ Leetcode

[Problem Solving] Spiral Matrix

Posted on May 27, 2020June 23, 2024 by Swetha Kannan

Given a matrix of m x n elements, return the elements in spiral order.

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Output: [1,2,3,6,9,8,7,4,5]

This problem is quite popular and is frequently asked during interviews.

Solution: To traverse the matrix in spiral order, we have to go along the boundaries starting from the top left element at i = 0, j = 0 where i, j represent the row and column indexes respectively. Let’s view the matrix as a collection of layers. Once we complete the outermost layer, we have to keep traversing the inner layers until no element is left to be visited. We can think of this as traversing multiple matrices in spiral order layer by layer.

What are some things to remember while traversing?

We need some indexes to track our traversal. A straightforward approach is to have four indexes to keep track of the four boundaries of the matrix. These will be called left, right, top and bottom.
We will be using a while loop to add elements to a results array as long as left < right and top < bottom. This indicates that there are still elements left to traverse.
Inside the while loop, we will be using four for loops to traverse each boundary.
Avoid adding duplicate elements when changing directions ie., once we finish traversing a row [1, 2, 3, 4, 5], we have to increment the row index to avoid adding 5 again during the right most column traversal. Similarly, right and bottom pointers should be decremented upon completing their respective boundary traversals.
This problem code is nothing fancy but a matter of writing clear code without getting confused with the indices. The best way to get it right is to write the for loops as you traverse an example asymmetric matrix. This is because, a symmetric matrices usually do not help us handle edge cases in matrix problems.
One corner case for this problem is when we are traversing a column matrix as shown below where m = 4, n = 1.

In this case, we first initialize these variables.

top = 0
bottom = m #4
left = 0
right = n #1

Top boundary: row = top = 0, col = left to right [0, 1). Results = [1]. Increment top pointer, top = 1.

Right boundary: row = top to bottom [1, 4), col = right – 1 = 0. Results = [ 1, 2, 3, 4]. Decrement right pointer, right = 0.

Now after the above two for loops, we are done traversing the entire matrix. But the next traversal will add duplicate elements to the results.

Bottom boundary: row = bottom – 1 = 3, col = right – 1 to left – 1 [0, -1). Results = [1, 2, 3, 4, 4]

This will attempt to traverse the bottom element 4 again. So right after traversing top and right boundaries, we have to always check whether left < right and top < bottom condition still holds true. In this case top < bottom since 1 < 4 but left = right since 0 = 0 indicating that we are about to traverse a boundary again.

Time Complexity: We will end up visiting each element of the matrix, so time complexity will be O(M * N).

Space Complexity: Constant variables are used to track boundaries, so no additional space is being used. The space complexity will be O(1).

Code:

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        top, bottom = 0, m
        left, right = 0, n
        
        results = []
        
        while top < bottom and left < right:
            
            # traverse top boundary
            for i in range(left, right):
                results.append(matrix[top][i])
            top += 1
                
            # traverse right boundary
            for i in range(top, bottom):
                results.append(matrix[i][right-1])
            right -= 1
            
            if top < bottom and left < right:
                # traverse bottom boundary
                for i in range(right - 1, left - 1, -1):
                    results.append(matrix[bottom-1][i])
                bottom -= 1

                # traverse left boundary
                for i in range(bottom - 1, top - 1, -1):
                    results.append(matrix[i][left])
                left += 1
            
        return results

Testing: The following cases are good to test for matrix problems.

Empty matrix: []
Empty rows: [[]]
Single value matrix: [[1]]
Two element matrix: [[1, 2]]
Column matrix: [[1,2,3,4]]
Row matrix: [[1],[2],[3],[4]]
Symmetric matrix: [[1,2,3, 4],[4,5,6, 8], [9,10,11,12],[13,14,15,16]]
Asymmetric matrix: [[1,2,3, 4],[4,5,6, 8]]

Want to try solving this problem? https://leetcode.com/problems/spiral-matrix/

Hope you enjoyed this post on traversing a matrix in spiral order. Have a great day!

Arrays and Strings, Data Structures/ Leetcode, Matrix problems

[Problem Solving] Diagonal Traverse

Posted on May 25, 2020June 23, 2024 by Swetha Kannan

Given a matrix of M x N elements, return the elements in diagonal order as shown below.

[
 [ 1, 2, 3, 4 ],
 [ 5, 6, 7, 8 ],
 [ 9, 10, 11, 12 ],
 [13, 14, 15, 16 ]
]

Output: [1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12, 15, 16]

Solution #1: To begin with, let’s ignore the part where alternate diagonal elements need to be reversed. Let’s try to traverse the matrix as shown above in image 2.

We see that a diagonal always starts either from the top row or the last column of elements. If we are given the starting point of a diagonal, how can we get to the next diagonal element?

For example, let’s say we are at 4 which is at (r = 0, c = 3) where r and c indicate the row and column indexes respectively. To get to the next element, we have to move one row down and one column to the left, ie., r = 1, c = 2. To generalize:

next_r = r + 1, next_c = c – 1

To match the expected results where alternate diagonal elements are reversed in order, we can collect the diagonal elements and reverse the order of alternate diagonals before adding to the results. The code below is an intuitive way of solving this problem.

def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        results = []
        row, col = 0, 0
        
        while row < m and col < n:
            
            temp = []
            
            # To collect all elements of a diagonal, keep going one row down and column 
            # to the left until we hit matrix boundaries
            i, j = row, col
            while i < m and j >= 0:
                temp.append(matrix[i][j])
                i += 1
                j -= 1
                
            # Reverse the order for alternate diagonals
            if (row + col) % 2 == 0:
                results.extend(temp[::-1])
            else:
                results.extend(temp)
                
            # Set row, col to traverse the next diagonal
            if col < n - 1:
                col += 1
            else:
                row += 1
                
        return results

Time Complexity: O(M*N) where M is the number of rows and N is the number of columns in the matrix

Space Complexity: The additional space used in this solution is the temp array which holds the diagonal elements. The largest diagonal of a matrix has min(M, N) elements, so space complexity is O(min(M, N)).

Testing: When it comes to matrix problems, make sure to test the following cases.

Empty matrix: []
Empty rows: [[]]
Single value matrix: [[1]]
Two element matrix: [[1, 2]]
Column matrix: [[1,2,3,4]]
Row matrix: [[1],[2],[3],[4]]
Symmetric matrix: [[1,2,3, 4],[4,5,6, 8], [9,10,11,12],[13,14,15,16]]
Asymmetric matrix: [[1,2,3, 4],[4,5,6, 8]]

Solution #2: The above solution is perfectly acceptable. If you notice the indices of diagonal elements, they all sum to the same number. Remember this pattern as it might come handy while manipulating diagonal elements of a matrix.

Keeping this in mind, here is an alternate solution to this problem where we use the sum of indices as keys in a dictionary to store values belonging to a particular diagonal.

import collections

def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        elements = collections.defaultdict(list)
        results = []
    
        for i in range(m):
            for j in range(n):
                elements[i+j].append(matrix[i][j])
                
        for k, v in elements.items():
            if k % 2 == 0:
                results.extend(v[::-1])
            else:
                results.extend(v)

        return results

Time Complexity: O(M*N)

Space Complexity: O(M*N)

Want to try solving this problem? https://leetcode.com/problems/diagonal-traverse/

Hope you enjoyed solving the diagonal traverse problem. Have a great day!

Arrays and Strings, Data Structures/ Leetcode

[Problem Solving] Plus one to array

Posted on May 23, 2020June 23, 2024 by Swetha Kannan

Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself.

Examples:

[1, 2, 3] should return [1, 2, 4]
[9, 9] should return [1, 0, 0]

Solution: When we add 1 to a single digit number, there are two outcomes. It can either remain a single digit number or results in 10. If the result is 10, we have to store 0 in the index i and propagate the carry 1 to the previous index i-1.

Let’s traverse the array from the end and add one to the value at index i.

If the value becomes 10, store 0 in nums[i] and continue traversing the array
Otherwise, add one to the value at nums[i] and return the array

Time Complexity: Since we traverse the array once, O(N)

Space Complexity: No additional space is used, so O(1)

def plusOne(self, digits: List[int]) -> List[int]:
        
        for i in range(len(digits)-1, -1, -1):
            
            if digits[i] + 1 == 10:
                digits[i] = 0
            else:
                digits[i] += 1
                return digits
            
        return [1] + digits #handle the case where all digits become 9

Testing: For most problems it’s good to test the following cases.

Empty array: []
Single value array: [1]
Array with two values: [1, 8]
A random array: [1, 2, 3, 4]

In this problem, there are two important cases to test. When the last digit is 9 and when all the digits are 9.

[1, 9]
[9] or [9, 9] or [9, 9, 9]

Want to try solving this problem? https://leetcode.com/problems/plus-one/

Hope you enjoyed this simple approach to the plus one problem. Have a great day!

Arrays and Strings, Data Structures/ Leetcode

[Problem Solving] Find Pivot Index

Posted on May 23, 2020June 23, 2024 by Swetha Kannan

Let’s say we are given an array of integers and we want to find a pivot index such that the sum of numbers to the left of this index equals the sum of numbers to the right.

Example: [1, 7, 3, 6, 5, 6]

1 + 7 + 3 = 5 + 6 = 11. In this example, the pivot value is 6, whose array index is 3. If no such index exists, return -1.

Solution #1: To get started with a brute force approach, let’s consider each number as a pivot and calculate the left and right side sums until they equal each other.

Pivot = 1, pivotIndex = 0, leftSum = 0, rightSum = 27

Pivot = 7, pivotIndex = 1, leftSum = 1, rightSum = 20

Pivot = 3, pivotIndex = 2, leftSum = 8, rightSum = 17

Pivot = 6, pivotIndex = 3, leftSum = 11, rightSum = 11. Voila!! Here leftSum = rightSum, so return 3 as the answer.

Time Complexity: A worst case scenario is when we have to traverse the entire array and the pivot index is the last index (n-1) of the array which will be O(N). Calculating left and right side sums adds another O(N) and so it will be an O(N²) algorithm. To improve our algorithm efficiency, we have to try to do this in linear time. In the previous approach, calculation of leftSum added to increased complexity, how can we optimize this part? What if we had access to the leftSum and rightSum values in advance?

Solution #2: Let’s pre-calculate the leftSum and rightSum values for each pivot and store these values in two arrays.

[1, 7, 3, 6, 5, 6]

leftSums = [0, 1, 8, 11, 17, 22, 28]

rightSums = [27, 20, 17, 11, 6, 0]

In leftSums and rightSums, we need to find the index whose values are equal, in this case it’s 11 ie., leftSums[3] = rightSums[3].

Time Complexity: In Solution #2, our time complexity will go down from O(N²) to O(N) since we use pre-calculated sum values to find the pivot index ie., O(N) for pre-calculation plus another O(N) while traversing to find pivot index .

Space Complexity: Using two extra arrays to pre-compute values adds additional 2N space. So the overall space complexity will be O(N).

Code for Solution #2:

def pivotIndex(self, nums: List[int]) -> int:
        
        if not nums:
            return -1
        
        n = len(nums)
        leftSums, rightSums = [0] * n, [0] * n
       
        for i in range(1, n):
            leftSums[i] = leftSums[i-1] + nums[i-1]
            
        for i in range(n-2, -1, -1):
            rightSums[i] = rightSums[i+1] + nums[i+1]
            
        for i in range(n):
            if leftSums[i] == rightSums[i]:
                return i
            
        return -1

Slight improvement on space complexity:

Anytime we are traversing an array both ways and then iterating it all over again, it’s possible to eliminate one of the traversals and calculate values on the fly. In the above code snippet, the following chunks of code are kind of doing the same thing, let’s try to avoid code duplication.

for i in range(1, n):
    leftSums[i] = leftSums[i-1] + nums[i-1]

for i in range(n):
    if leftSums[i] == rightSums[i]:
        return i

We can replace the above two blocks by calculating leftSum on the fly as shown below.

for i in range(0, n):

    if i > 0:
        leftSum += nums[i-1]
    if leftSum == rightSums[i]:
        return i

Time Complexity: O(N)

Space Complexity: O(N)

Testing: For array problems like these, it’s important to test the following cases.

Empty array: [] => returns -1
Single value array: [1] => returns 0
Double value array: [1, 2] => returns -1
A random array: [2, 3, 4, 5] => returns 2
All given test cases in the problem statement
Arrays that have one pivot index: [1, 7, 3, 6, 5, 6] => returns 3
Arrays that have more than one pivot index: [1, 0, 1, 0] => returns 0
Arrays with no pivot index: [1, 2, 3, 4] => returns -1

Can we do better? Yes!

Solution #3: Introducing prefix sum

If we are given the leftSum of a pivot, what else do I need to get the rightSum? The total sum of the array.

Example: [1, 7, 3, 6, 5, 6]

totalSum = 1 + 7 + 3 + 6 + 5 + 6 = 28

pivot = 7, pivotIndex = 1, leftSum = 1, rightSum = 28 – 1 – 7 = 20

pivot = 6, pivotIndex = 3, leftSum = 11, rightSum = 28 – 11 – 6 = 11

To generalize, rightSum(i) = totalSum – leftSum – nums[i]. Now let’s alter the code accordingly.

def pivotIndex(self, nums: List[int]) -> int:
        
        if not nums:
            return -1
        
        n = len(nums)
        leftSum = 0
        totalSum = sum(nums)
        
        for i in range(n):
            if leftSum == totalSum - leftSum - nums[i]:
                return i
            
            leftSum += nums[i]
            
        return -1

Time Complexity: O(N) for calculation sum of nums, O(N) for finding pivot index, so the overall time complexity will be O(N).

Space Complexity: O(1) since we use constant space to store totalSum and leftSum values.

Want to solve this problem? https://leetcode.com/problems/find-pivot-index/

Hope you enjoyed this step by step approach to iteratively improve upon a solution for a problem. Have a great day!