LeetCode Notes: Array

Here are some small notes for the following LeetCode solutions:

#1 Two Sum

We can iterate through the array and use a map (key: array value; value: array index) to store the values we’ve encountered. During the iteration, we check if we find the complement (target-current value) in the map. If it exists, we’ve found the answer; otherwise, we add the current value and its index to the map.

• Time Complexity: O(n)
• Space Complexity: O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(target - nums[i]) != null) {
                return new int[] {i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        return new int[] {};
    }
}

#121 Best Time to Buy and Sell Stock

We can use one variable to track the minimum buy price and another for the max profit. While iterating, if the current price is lower than the buy price, we update it. Otherwise, we can calculate the potential profit by subtracting buy price from the current price and update the max profit if it is higher than our current record.

• Time Complexity: O(n)
• Space Complexity: O(1)

class Solution {
    public int maxProfit(int[] prices) {
        int buy = 0;
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (i == 0 || prices[i] < buy) {
                buy = prices[i];
            }
            if (prices[i] - buy > profit) {
                profit = prices[i] - buy;
            }
        }
        return profit;
    }
}

#238 Product of Array Except Self

Basic Approach: The key idea is to use two arrays to store the needed information: one for storing the products of elements on the left-hand side, and the other for the right-hand side. Finally, we can generate a new array by multiplying the values from these two arrays.

Get chiang-sh’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Optimized Approach: We can optimize this by using only one array for the left-hand side products and a single variable for the right-hand side.

1. First loop: Generate the products of all elements to the left.
2. Second loop: Use a variable to keep track of the right-hand side product and calculate the final result directly in the same array.

By using this approach, we can reduce the extra space complexity to O(1).

• Time Complexity: O(n)
• Space Complexity: O(1)

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= right;
            right *= nums[i];
        }
        return answer;
    }
}

#53 Maximum Subarray

We can iterate through the array while maintaining the current sum. For each element, we add it to the current sum. If the current sum becomes negative, we reset it to 0 because a negative prefix will only decrease the sum of any subsequent subarray. Throughout the process, we keep track of and update the max sum whenever the current sum exceeds it.

• Time Complexity: O(n)
• Space Complexity: O(1)

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int total = 0;

        for (int num : nums) {
            if (total < 0) {
                total = 0;
            }

            total += num;
            if (total > max) {
                max = total;
            }
        }
        
        return max;
    }
}