Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums + nums == 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]
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.
O(n), where n is the number of elements in the array. Because we go through the array once.
O(n), because we store all elements of the array in the map.
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
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
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.
O(n), we move through the array only once.
O(1), we dont use any extra memory.
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:
O(nlogn)time but no extra space.
number -> countand check if count is more than 1. This take
O(n)time but also
Let's do the second approach since it takes lesser time.
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
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
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.
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 =  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
-> 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.
Return to Index