Arrays

Question 1

1. Two Sum

Given an array of integers nums and an integer target, return indices of two numbers such that they add up to target.

Assume each input would have exactly one solution and you may not use the same element twice

Answer 1

1. For loop through list
2. Number “to find” is target minus number of current index
3. Replace Value at current index with “x” or something that is not an integer
4. Search for number to find. If there is an index, return

Question 2

217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, return false if every element is distinct

Answer 2

1. Create hash set by iterating through nums

2 Return True if the length of hash set is not equal to the length of nums

Question 3

238. Product of Array Except Self

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

Answer 3

Still need to decide on a best solution for this

Question 4

53. Maximum Subarray

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

Answer 4

1. Instantiate variable to keep track of current sum
2. Instantiate variable to keep track of current max. Make this equal to the first value in the list so that in the case of 1 item in list, the max sum will just be the first number
3. Iterate through list.
4. Check to see if current sum is less than 0, if so just set current sum to 0 because we don’t need a negative prefix
5. add current number to current sum
6. update max sum to take the max between current sum and current max
7. return max sum

Question 5

152. Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Answer 5

1. Instantiate 2 variables to keep track of the current min and max. both should be set to 1 because we are dealing with multiplication and this will allow the first product to be equal to itself
2. Instantiate variable to keep track of the max product
3. Iterate through list of nums.
4. Check to see if the current number is 0, because everything subsequent to this 0 will be zero. if so, reset current min and max variables to be 1.
5. Create a temp max (or min) to take the current max (or min) because we are going to change the current max
6. Reassign the current max variable to take the max of current max * current num, current max * current num, and current num.
7. Reassign the current min variable to take the max of temporary max * current num, current min * current num, and current num
8. Reassign the max product variable to take the max of max product, current max and current min
9. return max product

Question 6

153. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

Answer 6

1. Instantiate 2 variables to keep track of left and right pointers. left will be 0, right will be len(list) - 1.
2. While left < right
3. find midpoint. Best formula for this is: mid = left + (right - left) // 2. this prevents overflow exceptions and the // will ignore the decimal value
4. Base case is if if mid > 0 and nums[mid] < nums[mid-1]. because if the the number to the left of the current number is greater than the current number, we know that this is where the row is rotated and the number to the right is the biggest number and the current number is the min number. if this is the case, return nums[mid]
5. Otherwise, if nums[left] <= nums[mid] and nums[mid] > nums[right]. This means that the left side is sorted and right side is not. Because the right is not sorted, we know the pivot is on the right side. as such, we move the left pointer to the right side of the mid point.
6. Otherwise, this means that the left side is not sorted and thus we will move the right pointer to the left of the mid point.
7. Lastly, return nums[left] because in step 5, we allowed nums[left] == mid. So if the mid check didn’t return, we will return the left number, which should be the mid.

Question 7

33. Search in Rotated Sorted Array

Answer 7

https://leetcode.com/problems/search-in-rotated-sorted-array/

Question 8

11. Container With Most Water

Answer 8

https://leetcode.com/problems/container-with-most-water/

Question 9

15. 3Sum

Answer 9

https://leetcode.com/problems/3sum/

Question 10

167. Two Sum II - Input array is sorted

Answer 10

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/