Arrays and Strings – Page 2

Binary Search variations that you should know

Posted on June 15, 2020 by Swetha Kannan

Binary Search is a useful algorithm to search for a target value in a sorted list of elements.

Standard Binary Search:

Get the middle element of the sorted list and compare with the target value. If the number equals the target, we found the value.
If the middle element is less than the target, then we have to search in the right half of the sorted array.
Else we search in the left half of the sorted array.

Let us look at the code for standard Binary Search.

def binarySearch(self, nums: List[int], target: int) -> int:

    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # search in the right half       
        if nums[mid] < target:
            left = mid + 1

        # search in the left half      
        else:
            right = mid - 1

    return -1

At each iteration of the while loop, the above algorithm divides our search space by half, so the overall time complexity will be O(log N). This is a significant reduction compared to the O(N) time complexity incurred by Linear Search. Now let’s look at a variation.

Binary Search Variation #1:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Assumption: There are no duplicates in the array.

In this case, if a target is not found, we have to find the index of the value immediately greater than the target. Let’s look at an example.

Input: nums = [1,3,5,6], target = 4

Output: 2

In the above example, 4 is not present in the array. If we were to insert it into the array, we should insert it between 3 and 5. So our insert index will be 2.

We can use the standard binary search to find the insert position with a slight variation. Let’s run through the algorithm step by step.

left = 0, right = 3
mid = (0 + 3) // 2 = 1
nums[mid] = nums[1] = 3
Here 3 < 4, if nums[mid] < target, search the right half of the list
Then left = mid + 1 => 1 + 1 = 2

left = 2, right = 3
mid = (2 + 3) // 2 = 2
nums[mid] = nums[2] = 5
Here 5 > 4, if nums[mid] > target, search the left half of the list
Then right = mid -1 => 2 – 1 = 1

In the above example, we see that the left pointer holds the insert position as we go through the while loop. This is because, by the time we complete the while loop, left pointer will point to the element that is immediately greater than the target value which is where we will insert our target.

Code:

def searchInsert(self, nums: List[int], target: int) -> int:

    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        if nums[mid] < target:
            left = mid + 1

        else:
            right = mid - 1

    return left

Binary Search Variation #2:

Now what if we have to find the index of the element that is just smaller than the given target ie., the greatest element lesser than the target value. Yes, you guessed it! This value is stored by the right pointer, so we return it in that case.

Code:

def searchLesserThanTarget(self, nums: List[int], target: int) -> int:

    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        if nums[mid] < target:
            left = mid + 1

        else:
            right = mid - 1

    return right

Hope you enjoyed learning the different variations of Binary Search. Have a great day!

Arrays and Strings, Data Structures/ Leetcode, June Leetcoding Challenge, Two Pointer Technique

[Problem Solving] Is Subsequence – Two Pointer Technique

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

Given two strings s and t, check if s is a subsequence of t. A subsequence can be formed by deleting some characters in a string without changing the order of the other characters.

Input: s = “abc”, t = “ahbgdc“
Output: true

The simplest way to solve this problem is to use the two-pointer technique where we designate two different pointers to traverse s and t simultaneously. If the characters match, then we move on to check the next character of s against t, otherwise we move on to the next character in t. By the time we are done, there should be no characters left in s to be compared and therefore s must be a substring of t.

Time Complexity: The loop ends when we run out of characters to compare in either s or t. The worst case happens when we run through all the characters in t, so the time complexity is O(T).

Space Complexity: O(1)

Code:

def isSubsequence(self, s: str, t: str) -> bool:

    i, j = 0, 0

    while i < len(s) and j < len(t):
        
        if s[i] == t[j]:
            i += 1
            
        j += 1
    return i == len(s)

Testing:

For this problem, the following test cases will cover various situations.

Empty s
Empty t
s string length greater than t
A few other random test cases

I find all other approaches to be kind of an overkill, so I hope you enjoyed this simple approach. Have a great day!

Arrays and Strings, Data Structures/ Leetcode, June Leetcoding Challenge

Queue Reconstruction by Height

Posted on June 6, 2020June 7, 2020 by Swetha Kannan

We are given a list of people described by height h and a number k. k refers to the number of people in front of this person who are of height greater than or equal to their height. We have to write an algorithm to reconstruct the queue.

The number of people will be less than 100.

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Explanation:

[7, 0] – Height = 7 and there should be 0 people equal in height or taller in front of this person

[4, 4] – Height = 4 and there should be 4 people equal in height or taller in front of this person

[7, 1] – Height = 7 and there should be 1 people equal in height or taller in front of this person

[5, 0] – Height = 5 and there should be 0 people equal in height or taller in front of this person

[6, 1] – Height = 6 and there should be 1 people equal in height or taller in front of this person

[5, 2] – Height = 5 and there should be 2 people equal in height or taller in front of this person

Solution:

There are two elements in each list item which is the height and k.

Input = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output = [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Let’s manually try to place the people in a queue. The given list looks like this.

We first take the tallest person and place them in the queue according to their index value. If two people have the same index value, then we give priority to the person who is shorter. We will see why in a bit. So the queue will look like this after placing [7, 0] and [7, 1].

Next, we pick the next tallest person in queue [6, 1]. When we try to place them in the index 1, there is already a person of height 7 there. In this case, we need to place the person with the shorter height in front because they should have only 1 more person who is of equal height or is taller than them. We insert this person in the queue before [7, 1]. The queue will now look like this.

We can pick the next tallest person with height 5. We can place [5, 0] before placing [5, 2] since the lower index person gets priority. 0th index already has a person of height 7, but we will push them back and insert [5, 0] to let the shorter person be in the front. The queue will now look like this.

Let’s continue doing this for the left out elements and we will get the following.

The code for this algorithm involves two steps:

Arrange people in descending height. When there is a tie in height, give priority to the one with the lower index.
Insert people according to their indexes into a new queue. When there is a tie in index, give priority to the one with the lower height.

Time Complexity: O(NlogN) for sorting and O(N) to insert an element into a list, so the overall complexity to insert N elements will be O(N²).

Space Complexity: We will do the sorting in place and the result queue need not be considered as extra space, so space complexity is O(1).

Code for the above solution:

def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:

    # sort people by descending height and ascending index k
    people.sort(key = lambda x: (-x[0], x[1]))

    results = [] * len(people)

    for p in people:
        results.insert(p[1], p)

    return results

Hope you enjoyed reading this post. Have a great day!

Arrays and Strings, Data Structures/ Leetcode, June Leetcoding Challenge

Random pick with weight – a probability problem

Posted on June 5, 2020June 7, 2020 by Swetha Kannan

Today’s problem is a very interesting one but is usually worded poorly in most places.

We are given an array W of positive integers where W[i] refers to the weight of index i. We have to write a function called pickIndex which will randomly pick an index proportional to its weight. Let’s look at an example to understand this better.

W = [1, 2, 3, 4, 5]

In the above case the weights are as follows.

W[0] = 1

W[1] = 2

W[2] = 3

W[3] = 4

W[4] = 5

How do we randomly pick an index proportional to its weight?

The weights of all the indexes in the array sum to 15 (1 + 2 + 3 + 4 + 5).

For index i = 0 with weight = 1, we have to pick this index once out of 15 times

For index i = 4 with weight = 5, we have to pick this index five out of 15 times

The bottomline line is that the indexes with the higher weights should have high probability of being picked, in this case that probability is:

P(i) = W[i] / sum(W)

ie., for index = 4 P(4) = 5/ 15 = 1/ 3.

Solution #1:

For probability problems, one of the foremost things we need is a sample space. Let’s simulate this using a generated array with 15 entries where each entry corresponds to an index in the array and appears W[i] number of times. For example, the index 4 should appear W[4] = 5 times in the array.

Sample space = [0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4]

If we are to pick a number randomly from the above list, we have solved the problem of picking a random index proportional to its weight.

Time Complexity: The time complexity will be O(sum(W)) to generate the sample space array.

Space Complexity: The simulated array will cost us O(sum(W)) extra space.

Code for solution #1:

class Solution(object):

    def __init__(self, w: List[int):

        totalSum = sum(w)
        table = [0] * totalSum
        
        i = 0
        for j in range(0, len(w)):
            for k in range(i, i + w[j]):
                table[k] = j
            i = i + w[j]
            
        self.size = len(table)
        self.table = table
        

    def pickIndex(self) -> int:
        randomIdx = random.randint(0, self.size - 1)
        
        return self.table[randomIdx]
        

# Your Solution object will be instantiated and called as such:
obj = Solution(w)
param_1 = obj.pickIndex()

The above solution is extremely memory intensive since we generate an array that’s mostly larger than the input array itself to simulate the sample space.

Solution #2:

The total sum of our weights sum(W) is 15. If we had to draw a line and divide it according to the given weights ranging from 1 to 15, how would that look like?

W = [1, 2, 3, 4, 5]

sample_space = [0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4]

Instead of generating an entirely new array with the repeated indexes, we can calculate the prefix sums for each index. The formula to find the prefix sum of W[i] is shown below.

W[i] = W[i] + W[i-1]

Then our prefix array will look like this.

W = [1, 3, 6, 10, 15]

The total weight 15 is the length of our sample space. We will first generate a random number between 1 and 15.

randIndex = random.randint(1, maxWeight)

Let’s say that the randIndex returns 8. This index falls in the range (6 – 10]. So we return the index filling up this range which is 3.

If the randIndex returns 15, this number falls in the range (10 – 15]. So we return the index filling up this range which is 4.

We find this range using linear search on the prefix sum W array. All we have to find a value such that value <= randIndex which indicates that it has fallen in that particular range. In that case, we return the index of this value.

Time Complexity: O(N) to calculate prefix sum and O(N) to find the randIndex value in the prefix sum array. This means the pickIndex function call runs in O(N) time.

Space Complexity: O(1) since we are not using any extra space.

Code for solution #2:

class Solution:

    def __init__(self, w: List[int]):

        # Calculate the prefix sums
        w = list(itertools.accumulate(w))
        self.w = w

        if self.w:
            self.maxWeight = self.w[-1]
        else:
            self.maxWeight = 0

    def pickIndex(self) -> int:

        randIndex = random.randint(1, self.maxWeight)

        for i, prefixSum in enumerate(self.w):
            if randIndex <= prefixSum:
                return i

        return 0
        
#Your Solution object will be instantiated and called as such:
obj = Solution(w)
param_1 = obj.pickIndex()

Solution #3:

In the above solution pickIndex() runs in O(N) time and it’s basically doing a linear search in the array to find the range of the randIndex. We can improve the time complexity using binary search.

In the binary search algorithm, if our randIndex value matches an entry in the prefix sums array, we return that index. Else we return the index of a value which is <= randIndex. This is basically a binary search to find a number N such that N <= target.

Time Complexity: O(logN) to pick the index.

Space Complexity: O(1)

Code for solution #3:

class Solution(object):

    def __init__(self, w: List[int]):
  
        w = list(itertools.accumulate(w))
        self.w = w

        if self.w:
            self.maxWeight = self.w[-1]
        else:
            self.maxWeight = 0
          
    
    def pickIndex(self) -> int:
  
        randIndex = random.randint(1, self.maxWeight)
        
        # Binary search for randIndex
        left = 0
        right = len(self.w) - 1
        
        while left <= right:
            mid = (left + right) / 2
            
            if self.w[mid] == randIndex:
                return mid
            
            if self.w[mid] < randIndex:
                left = mid + 1
            else:
                right = mid - 1
                
        return left
               
# Your Solution object will be instantiated and called as such:
obj = Solution(w)
param_1 = obj.pickIndex()

Solution #4 (Optional):

The code in solution #3 can be written in a very pythonic way using built-in functions as shown below. The time and space complexity will be the same.

Python’s bisect.bisect_left() returns an insertion point i that partitions the array into two halves such that all(val < randIndex for val in w[left : i]) for the left side and all(val >= randIndex for val in a[i : right]) for the right side. Read more here.

class Solution:
    def __init__(self, w: List[int]):
        self.w = list(itertools.accumulate(w))

    def pickIndex(self) -> int:
        return bisect.bisect_left(self.w, random.randint(1, self.w[-1]))
        
#Your Solution object will be instantiated and called as such:
obj = Solution(w)
param_1 = obj.pickIndex()

Hope you learnt to methodically approach the random pick with weight problem. Have a nice day!

Arrays and Strings, June Leetcoding Challenge, Python

5 Pythonic ways to reverse a string

Posted on June 4, 2020 by Swetha Kannan

Write a function that reverses a string. The input string is given as an array of characters char[].

Input: A = [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]

Solution #1: Arrays ie., lists in Python are mutable data structures which means they can be modified in place without having to allocate extra space. For this problem, creating a new array using the input array is a trivial solution. So let’s directly dive into an O(1) memory solution.

In Python, we can refer to the elements in reverse order starting at the index -1.

A[-1] = “o”

A[-2] = “l”

A[-5] = “h”

This is quite helpful in manipulating array indexes. In order to reverse the elements, we don’t have to traverse the full list but swap the first half of the list with the second half starting from the end.

ie., swap A[i] with A[-(i+1)] for i = 0 to i = len(A) / 2

Time Complexity: We traverse only half the list while swapping elements with the second half of the list. So the time complexity will be O(N/2) which is O(N) overall.

Space Complexity: O(1)

Code for solution #1:

def reverseString(self, s: List[str]) -> None:
    """
    Do not return anything, modify s in-place instead.
    """
    for i in range(len(s) // 2):
        s[i], s[-(i+1)] = s[-(i+1)], s[i]

Solution #2: A Python in-built function that does exactly what we did above is reverse(). The list is modified in place by swapping the first half of the list with the second half the same way as shown above. Read more about reverse() here.

Code for solution #2:

def reverseString(self, s: List[str]) -> None:
    s.reverse()

Time Complexity: O(N)

Space Complexity: O(1)

Solution #3: If we are allowed to create and return a new list, then we can use Python reversed() function as shown below. reversed() returns an iterator in Python, so we have to wrap its result in a list(). Read more about it here.

Code for solution #3:

def reverseString(self, s: List[str]) -> List[str]:
    return list(reversed(s))

Time Complexity: O(N)

Space Complexity: O(N) since we are creating a new list.

What if we are given a string and not an array of characters?

An important distinction here is that strings are immutable, so we cannot leverage any in-place reversals here. Let’s look at some Pythonic ways of reversing a string.

Input: “hello”

Output: “olleh”

Solution #4: Using Python’s elegant index slicing.

Code for solution #4:

def reverseString(self, s: str) -> str:
    return s[::-1]

Okay, what was that? In Python there is a concept called slicing. The syntax for slicing is shown below.

A[start: stop: step]

start – The index to start slicing (default: 0)
stop – The index to stop slicing (default: len(s))
step – The increment between each index for slicing

Examples:

A[0:1] slices the first element
A[1:4] slices the elements from index 1 to 3

The -1 step in the code indicates that we will start at the end and stop at the start instead of the other way around, thereby reversing the string.

Input	Method	Time Complexity	Space Complexity
list[str]	Swap elements from first half with second half of the array.	O(N)	O(1)
list[str]	Built-in list.reverse()	O(N)	O(1)
list[str]	list(reversed(s))	O(N)	O(N)
str	Slicing str[: : -1]	O(N)	O(N)
str	“”.join(reversed(str))	O(N)	O(N)

[Problem Solving] Two City Scheduling

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

We are given a list of costs as shown below.

costs = [[10, 20], [30, 200], [400, 50], [30, 20]]

The cost of flying the i^th person to city A is costs[i][0]
The cost of flying the i^th person to city B is costs[i][1]

A company is planning to interview 2N people. Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

Example:

Input: [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Assumption:

The costs list will always have an even length.

Solution:

First let’s try to understand the problem statement clearly.

What we need to do is out of N given people and their costs, exactly N/2 people should be flown to city A and other N/2 people need to be flown to city B.
This means for N/2 elements in the costs list, we have to choose the costs[i][0]^thelement and for the other N/2 elements, we need to choose the costs[i][1]^th element.
The part that needs to be solved is to choose elements such that the overall cost is minimized.

The first thing that pops in our heads is to find out if we can somehow sort this given list. Let’s look at an example.

[[10, 20], [10, 20], [10, 40], [10, 50]]

We can sort by the first element of the list of lists ie., costs[i][0]. This will ensure that the list is sorted by the lowest costs to fly to city A. In this case, the list remains the same.

[[10, 20], [10, 20], [10, 40], [10, 50]]

If we choose the first N/2 people this way to fly to city A and the next N/2 people to fly to city B, we are not guaranteed that the sum of costs to fly to B will be minimum.

Sum(A) = 10 + 10 = 20

Sum(B) = 40 + 50 = 90

Total cost = 20 + 90 = 110 Wrong answer!

In order to get the optimal cost, we have to fly the first two people to city B and the next two to city A. Remember that we cannot fly the same person to both city A and city B!!

Sum(A) = 10 + 10 = 20

Sum(B) = 20 + 20 = 40

Total cost = 20 + 40 = 60 Voila!

Using the given elements in the list, we cannot directly sort it such that the cost is minimized. So, what can we do with the given values? Let’s look at the costs on a case by case basis.

[10, 20] – The cost of sending this person to city A vs city B is 10 – 20 = -10

[10, 40] – The cost of sending this person to city A vs city B is 10 – 20 = -30

[10, 50] – The cost of sending this person to city A vs city B is 10 – 20 = -40

Since we are subtracting cost(B) from cost(A), if the difference is low, it means it’s better to send this person to city A and when the difference is very high, we send them to city B. Now let’s say we have costs for a person as [400, 50]. The cost of sending this person to city A vs city B (cityA – cityB) is +$350!! We might as well send them to city B. So that’s what we will do.

We will sort the costs by the difference cost(A) – cost(B) from low to high. For the first N/2 people of this sorted list, we send them to city A and for the next N/2, we send them to city B.

Time Complexity: Sorting takes O(N log N), so this will be O(N log N) + O(N/2) + O (N/2). So the overall complexity is O(N log N).

Space complexity: If we are doing an in-place sort, then the space complexity will be O(1)

Code for the above solution:

def twoCitySchedCost(self, costs: List[List[int]]) -> int:

    minCost = 0
    N = len(costs)

    costs.sort(key = lambda x: x[0] - x[1])
    for i in range(N // 2):
        minCost += costs[i][0]

    for i in range(N // 2, N):    
        minCost += costs[i][1]

    return minCost

Testing:

You can test the following cases.

Any given test case: [[10,20],[30,200],[400,50],[30,20]]
Case where cost to city A is the same and vice versa: [[10,20],[10,20],[10,40],[10,50]]
Case where cost(A) = cost(B): [[10,10],[200,200],[400,400],[30,30]]
A random case mixed with the above two cases: [[20,10],[400,200],[100,400],[3,30], [3,30],[40,40]]

Hope you learnt how to solve the two city scheduling problem. Have a nice day!

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!