https://leetcode.com/problems/squares-of-a-sorted-array/

Problem Statement

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decrMeasing order.

Example 1:

Input: [-4,-1,0,3,10]

Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]

Output: [4,9,9,49,121]

Problem Analysis

The input of this problem is an 1-D array. Also please notice that the input array is sorted and non-decreasing. Usually when you see an input is sorted, you will always use this nature to resolve the problem. Also we are required to return the result in a sorted non-decreasing order. Since we are required to return a sorted result, I started to wonder whether the time complexity is O(N * lgN) since this is usually the minimal time complexity of algorithms that involve sorting. However, the nature of input array being sorted might also help us to improve the time complexity as well. Let’s think about this problem with all these questions in mind.

Thinking Process

We are given a sorted array A as input. We have to find the square of each elements in A and return the result of such an array in a sorted order. If all the elements in A are greater or equal to 0, we can just simply square every element and return the result. This will bring us the O(N) solution.

However, the exception is that the input list is not guaranteed to be positive. There could be negative numbers. Some negative numbers could have higher integer than some positive numbers. If we simply keep the original order of the input array and square every number up, then as the last step, sort the array and return it, we will get a O(N * lgN) time complexity answer. Let’s see how that’s implemented.

First Solution

1
2
3
4
5

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        for i in range(len(A)):
            A[i] *= A[i]
        return sorted(A)

or to be more pythonic (with worse space complexity):

1
2
3

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        return sorted([i * i for i in A])

https://leetcode.com/problems/flipping-an-image/

Problem Statement

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] >horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] >results in [1, 0, 0].

Example 1:

Input: [[1, 1, 0], [1, 0, 1], [0, 0, 0]]

Output: [[1, 0, 0], [0, 1, 0], [1, 1, 1]]

Explanation: First reverse each row: [[0, 1, 1], [1, 0, 1], [0, 0, 0]].

Then, invert the image: [[1, 0, 0], [0, 1, 0], [1, 1, 1]]

Example 2:

Input: [[1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1], [1, 0, 1, 0]]

Output: [[1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 0, 1], [1, 0, 1, 0]]

Explanation: First reverse each row: [[0, 0, 1, 1], [1, 0, 0, 1], [1, 1, 1, 0], [0, 1, 0, 1]].

Then invert the image: [[1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 0, 1], [1, 0, 1, 0]]

Problem Analysis

The input is a matrix which means that we are dealing with a 2-D array. 2-D array in python can be implemented as 2-D list. 2-D list is a list of list. The inner list represents the elements in each row and the outer list represents all the rows. We are asked to do two things, one is to flip the matrix and also invert the value. We can quickly think this as a minimum O(M * N) time complexity algorithm, where M and N represents the dimension of the matrix, because we have to go through each elements in the list. Space complexity is unknown until we know how can we flip the matrix.

Thinking Process

The steps are very obvious: flip and then invert. Let’s think about it one by one.

How should we flip a list in python? There are couple ways to do it:

1. Use built-in function reversed()

2. Use List class method reverse()

3. Use List slicing [::-1]

We will talk about the differences between them in the takeaways section. We will just choose one to use.

After knowing how should we flip a single list, we should think about how should we flip the whole matrix. The answer is very obvious. Row by row.

We also have to invert each 0 to 1 and 1 to 0. This can be done by using 1 - value.

Now it’s clear to us the we should iterate through each row of the matrix and flip them. At the same time, we should invert the values. Let’s see what’s the most intuitive solution:

First Solution

1
2
3
4
5
6
7

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        for row in A: # Iterate through each row in A
            row.reverse() # We flip each row
            for i in range(len(row)):
                row[i] = 1 - row[i] # Invert the value
        return A

https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/

Problem Statement

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1. After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]

Output: [18,6,6,6,1,-1]

Problem Analysis

Our input for this problem is an array and we are required to replace every element in the array with another number. This means that we have to iterate through the array for at least once. This yields at least O(N) time complexity. We also noticed that the last element is always -1. What we have to return is the modified array or a new array. This means that if we can modify the array in-place, we could reach a O(1) space complexity.

Thinking Process

The very intuitive solution is to start from the first element in the array and move to the right one by one. At each element, we find the maximum number on the right. However, it’s easy to get the time complexity of this algorithm which will be O(N^2). This is way too slow.

The question to ask is why do we have to iterate through each element on the right of the current index? Because we have to find the current maximum on the right every time we move the index. Is there anyway for us to find the current maximum on the right without iterating through the sub-array to the right of the index? Yes, we can start from the last element of the array. Every time we move the index to the left by one, we have already known what’s the maximum from the right-most point to the current index. This easily yields the following O(N) answer:

First Solution

1
2
3
4
5
6
7

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        cur_max = -1 # We keep track of what's the current maximum number from the right-most point.
        # cur_max is initialized to -1 because the last element is -1.
        for i in range(len(arr)-1, -1, -1):
            arr[i], cur_max = cur_max, max(cur_max, arr[i])
        return arr

• List Concatenation

  There are two ways two concatenate a list with another. One is to use + to concatenate a list. Another way is to use extend() function to concatenate

  1 2 3 4 5 6 7 8 9

  # Use + to concatenation a list A = ['a', 'p', 'p', 'l', 'e'] B = ['b', 'a', 'n', 'a', 'n', 'a'] C = A + B print(C) # ['a', 'p', 'p', 'l', 'e', 'b', 'a', 'n', 'a', 'n', 'a'] # Use extend() function to concatenate A.extend(B) print(A) # ['a', 'p', 'p', 'l', 'e', 'b', 'a', 'n', 'a', 'n', 'a']

  Read More

https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/

Problem Statement

Given an integer n, return any array containing n unique integers such that they add up to 0.

Problem Analysis

We firstly note that the input is an integer n and output is an array. Furthermore, we find that the output is not unique, which means that we have to construct an output that meet the requirement of the problem and there could be multiple or even infinite number of correct answers to this problem. This is rarely seen in a coding interview.

Another important thing that we notice from the question statement is that elements we use in the answer must be unique, which means we cannot reuse any of the element.

Thinking Process

Firstly we noticed that we need to construct an array that sums to 0. It’s really natural to think about the following way of constructing the array:

[-n, -n-1, -n-2, …, -3, -2, -1, 0, 1, 2, 3, …, n-2, n-1, n]

Since we need n elements in the array, which means we need n/2 elements on the positive side and n/2 on the negative side so that they can easily sum up to zero. The dealbreaker here is whether we need to include 0 in the array. On which circumstances do we need to include 0? When n is odd. Otherwise we don’t need 0. With this thinking process, it’s very easy to come up with the following naive solution:

First Solution

1
2
3
4
5
6
7

class Solution:
    def sumZero(self, n: int) -> List[int]:
        answer = [] # We construct an empty array to hold the result
        for i in range(1, (n//2) + 1):
            answer.extend([i, -i])
        if n % 2 != 0: answer.append(0) # We add 0 when n is odd
        return answer