Questions

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

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

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

On Leetcode

Two considerations - there is only one solution - an element can only be used once

Which means we can fix a number and see if its compliment exists in the array. To make it a linear time solution, we can use a map (number -> index) to look up the complement. One thing we have to keep in mind is NOT to make a pair with the same index.

Implementation: TwoSum

Time complexity

O(n), where n is the number of elements in the array. Because we go through the array once.

Space complexity

O(n), because we store all elements of the array in the map.

Best Time to Buy and Sell Stock

Leetcode

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

To re-iterate the questions, we need to take an element and see if there's a complement that exists between i+1 and n, whose difference is the max difference. However, if the max difference is <0, we need to return 0.

The naive solution that comes to mind is take an element and run another loop from i+1 to n and keep track of the max difference. This would give us a time complexity of O(n^2). Let's see if we can do better.

Now, we need to track the max difference. A max difference is only possible between the min element and the max element to the right of the min element. As we iterate through the array, we can know the min element so far. If we consider every element we consider as we traverse through the array as a candidate element that will give the max difference, we can keep a running max difference, which by the end of the array will give us the actual max difference.

Let's do a dry-run:

7,1,5,3,6,4

at 7, min = 7, maxDiff = 0
at 1, min = 1, maxDiff = 0
at 5, min = 1, maxDiff = 4
at 3, min = 1, maxDiff = 4
at 6, min = 1, maxDiff = 5
at 4, min = 1, maxDiff = 5

where 5 is the best profit we can get for this stock.

Implementation: Stocks

Time complexity

O(n), we move through the array only once.

Space complexity

O(1), we dont use any extra memory.

Contains Duplicate

Leetcode

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

The issue with finding duplicates in NOT O(n^2) time here is that we'd need to search the whole array to check if the current element has a duplicate. Couple of ways to avoid doing that would be:

  1. Sort the whole array, then duplicate elements would be next to each other. However, this takes O(nlogn) time but no extra space.
  2. Keep a map of number -> count and check if count is more than 1. This take O(n) time but also O(n) space.

Let's do the second approach since it takes lesser time.

Implementation: ContainsDuplicate

Time complexity

O(n)

Space complexity

O(n)

Product of Array Except Self

Leetcode

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

The naive way to find the product of all numbers except the element would be a O(n^2) algorithm. But we need to do it in O(n) time.

One observation we can make is:

1,2,3,4,5

Let's take a random element, say 3. The product for 3 is 40 (1*2*4*5). We can observe that its the product of all elements to the right of 3 and all elements to the left of 3. 

So, we can do one pass to find product of all numbers to the left and a similar pass to do product of all numbers to the right.

Implementation: ProdOfArray

Time complexity

O(n)

Space complexity

O(n)

Maximum Subarray

Leetcode

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

The question is where is the subarrray going to start. Lets take the example -2,1,-3,4,-1,2,1,-5,4,

-> If we start from `-2`, we keep `-2`, which is the highest we have seen so far
-> For 1, the sum now is -1. Between 1 and -1, we know a higher series can only start from 1
-> For -3, the sum is -2, we still think a series could start from 1
-> For 4, the sum is 2, we know a higher series can start from 4
-> For -1, the sum is 3, still think the series can start from 4
-> For 2, the sum is 5, still think the series can start from 4
-> For 1, the sum is 6, still think the series can start from 4
-> For -5, the sum is 1, still think the series can start from 4
-> For 4, the sum is 5, still think the series can start from 4

So at each point, is the current number is greater than the running sum, we ignore the series seen so far. This is because we know if we start with the current number, we will always get a higher series. Otherwise, we continue.

Implementation: MaximumSubarray

Time complexity

O(n)

Space complexity

O(1)

Return to Index