arrays – That Girl Coder

[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!