Leetcode 55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Analysis:

Typical greedy algorithm.

We need to have  a global maxReach. Then go through the whole array. Update the maxReach value between itself and nums[i] + i. Then check if it’s greater than nums.length – 1

Time complexity: O(n)

Space complexity: O(1)

Code is below:

public class Solution {
    public boolean canJump(int[] nums) {
        // O(n)
        
        if (nums == null || nums.length == 0) {
            return false;
        }
        
        int maxReach = 0;
        for (int i = 0; i < nums.length && i <= maxReach; i++) {             maxReach = Math.max(maxReach, nums[i] + i);             if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        
        return false;
    }
}

Leetcode 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

click to show more practice.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle

Analysis:

Keep two values, one is the sum for all values. One is the global max sum. If the sum is less than 0, make it to be 0.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

public class Solution {
    public int maxSubArray(int[] nums) {
        // O(n)
        
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int max = Integer.MIN_VALUE;
        int sum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, sum);
            sum = Math.max(sum, 0);
        }
        
        return max;
    }
}

Leetcode 73. Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Analysis:

We can check the first row/col, if we find 0’s , then we mark it true. Then go over the whole matrix, if we find any num to be 0. Mark all col/row to be 0. Then we go over the first row/col and if we find 0, we mark all value 0. Lastly, check the first row/col again and in case we miss something.

Time complexity: O(mn)

Space complexity: O(1)

Code is below:

public class Solution {
    public void setZeroes(int[][] matrix) {
        // O(mn)
        
        if (matrix == null || matrix.length == 0 || 
            matrix[0] == null || matrix[0].length == 0) {
                return;
            }
            
        int m = matrix.length;
        int n = matrix[0].length;
        boolean isRowZero = false;
        boolean isColZero = false;
        
        // check whether zeros in first row and col
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                isColZero = true;
                break;
            }
        }
        
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                isRowZero = true;
                break;
            }
        }
        
        // Go through rows and cols other than 1st
        // If we find zero value, set the corresponding first row/col 0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        // Check it again to make row/col other than 1st to be 0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        if (isRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        
        if (isColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        
    }
}

Leetcode 48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Analysis:

Use some math magic?

Time complexity: O(n ^ 2)

Space complexity: O(1)

Code is below:

public class Solution {
    public void rotate(int[][] matrix) {
        // O(n^2)
        
        if (matrix == null || matrix.length == 0 ||
            matrix[0] == null || matrix[0].length == 0) {
                return;
            }
            
        int len = matrix.length;
            
        for (int i = 0; i < len / 2; i++) {
            for (int j = 0; j < (len + 1) / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len - j - 1][i];
                matrix[len - j - 1][i] = matrix[len - i - 1][len -j - 1];
                matrix[len - i - 1][len -j - 1] = matrix[j][len - i - 1];
                matrix[j][len - i - 1] = temp;
            }
        }
        
    }
}

Leetcode 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?

Analysis:

The basic (two-pass) way is to count the occurrence of 0, 1 and 2. Then overwrite the corresponding value.

A better (one-pass) way is to use three pointers. One is for left, one is right and one is the index.

If we encounter 0, we swap it with the left value, left++, index++; if we encounter 1, index++; if we encounter 2, swap it with the right value, right–;

Time complexity: O(n)

Space complexity: O(1)

An example for this algorithm is :

1 0 2 2 1 0
    ^         ^
    L         H
    M

    Mid != 0 || 2
    Mid++

    1 0 2 2 1 0
    ^ ^       ^
    L M       H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 1 2 2 1 0
      ^ ^     ^
      L M     H

    Mid == 2
    Swap High and Mid
    High--

    0 1 0 2 1 2
      ^ ^   ^
      L M   H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 0 1 2 1 2
        ^ ^ ^
        L M H

    Mid == 2
    Swap High and Mid
    High--

    0 0 1 1 2 2
        ^ ^
        L M
          H

    Mid <= High is our exit case

Code is below:

public class Solution {
    public void sortColors(int[] nums) {
        // O(n)
        
        if (nums == null || nums.length == 0) {
            return;
        }
        
        int left = 0; 
        int right = nums.length - 1;
        int i = 0;
        
        while (i <= right) {
            if (nums[i] == 0) {
                swap(nums, i, left);
                left++;
                i++;
            } else if (nums[i] == 2) {
                swap(nums, i, right);
                right--;
            } else {
                i++;
            }
        }
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Leetcode 238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Analysis:

To get the products of all others, we can have an array of the same length. Then go through the array, get all products for all lefts. Then Go from the back and multiply all values on the right.

Note: we need to set up the first value res[0]  to be 1 initially.

Time complexity: O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        // O(n) O(1)
        
        if (nums == null || nums.length == 0) {
            return nums;
        }
        
        int[] res = new int[nums.length];
        int left = 1;
        int right = 1;
        
        res[0] = 1;
        
        // Get the product of all lefts
        for (int i = 1; i < nums.length; i++) {             left = left * nums[i - 1];             res[i] = left;         }                  // Go from the back, get the product of all rights         for (int i = nums.length - 2; i >= 0; i--) {
            right = right * nums[i + 1];
            res[i] = right * res[i];
        }
        
        return res;
    }
}

Leetcode 121. Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Analysis:
Go through the whole array and maintains the min value and the max profit.

Time complexity: O(n)
Space complexity: O(1)

Code is below:

public class Solution {
    public int maxProfit(int[] prices) {
        // O(n) 
        
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        // The smallest value and the profit
        int min = Integer.MAX_VALUE;
        int profit = 0;
        
        for (int price : prices) {
            // update the min value and the max profit
            min = price < min ? price : min;             profit = (price - min) > profit ? price - min : profit;
        }
        
        return profit;
    }
}

Leetcode 54 & 59. Spiral Matrix I & II

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

Analysis:

Try to follow the steps from left to right, to bottom to left to up.

Note to consider the situations where row/col = 1

Time complexity: O(mn)

Space complexity: O(1)

The code is below:

public class Solution {
    public List spiralOrder(int[][] matrix) {
        // O(mn)
        List result = new ArrayList<>();
        
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }
        
        int row = matrix.length;
        int col = matrix[0].length;
        int x = 0;
        int y = 0;
        
        while (row > 0 && col > 0) {
            // Only one row
            if (row == 1) {
                for (int i = 0; i < col; i++) {
                    result.add(matrix[x][y++]);
                }
                break;
            }
            
            // Only one col
            if (col == 1) {
                for (int i = 0; i < row; i++) {
                    result.add(matrix[x++][y]);
                }
                break;
            }
            
            // Move from top to right
            for (int i = 0; i < col - 1; i++) {
                result.add(matrix[x][y++]);
            }
            
            // Move from right to bottom
            for (int i = 0; i < row - 1; i++) {
                result.add(matrix[x++][y]);
            }
            
            // Move from bottem to lef
            for (int i = 0; i < col - 1; i++) {
                result.add(matrix[x][y--]);
            }
            
            // Move from left to top
            for (int i = 0; i < row - 1; i++) {
                result.add(matrix[x--][y]);
            }
            
            row -= 2;
            col -= 2;
            x++;
            y++;
        }
        return result;
    }
}

Followup:
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

Analysis:
Similar to the first question.

Time complexity: O(mn)

Space complexity: O(1)

Code is below:

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        
        int num = 1;
        int x = 0;
        int y = 0;
        int row = n;
        int col = n;
        
        while (num <= n * n) {
            // one row/col
            if (row == 1 || col == 1) {
                matrix[x][y] = num;
                break;
            }
            
            // top to right
            for (int i = 0; i < col - 1; i++, num++) {
                matrix[x][y++] = num;
            }
            
            // right to bottom
            for (int i = 0; i < row - 1; i++, num++) {
                matrix[x++][y] = num;
            }
            
            // bottom to left
            for (int i = 0; i < col - 1; i++, num++) {
                matrix[x][y--] = num;
            }
            
            // left to top
            for (int i = 0; i < row - 1; i++, num++) {
                matrix[x--][y] = num;
            }
            
            row -= 2;
            col -= 2;
            x++;
            y++;
        }
        
        return matrix;
    }
}

Leetcode 88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Analysis:

It’s hard to compare the two arrays from the beginning. So we compare them from the end. Then add the larger one to the end.

Note, after the whole process, we need to check whether there’s some leftover that we need to handle.

Time complexity: O(n)

Space complexity: O(1)

The code is below:

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // O(m + n) O(1)
        
        // Go from the back, add number 1 by 1
        int i = m - 1;
        int j = n - 1;
        int index = m + n - 1;
        
        while (i >= 0 && j >= 0) {
            if (nums1[i] >= nums2[j]) {
                nums1[index--] = nums1[i--];
            } else {
                nums1[index--] = nums2[j--];
            }
        }
        
        // Left over
        while (i >= 0) {
            nums1[index--] = nums1[i--];
        }
        
        while (j >= 0) {
            nums1[index--] = nums2[j--];
        }
    }
}

Leetcode 283. Move Zeroes

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.

2. Minimize the total number of operations.

Analysis:

To move all 0s to the end, we need to go through the whole array. If the value is not zero, then put it in the array. Afterwards, put all values to be 0.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

public class Solution {
    public void moveZeroes(int[] nums) {
        // O(n) O(1)
        
        if (nums == null || nums.length == 0) {
            return;
        }
        
        //Go through the array and put all non-zero element
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index++] = nums[i];
            }
        }
        
        //Put all arrays left equal to zero
        for (int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}