Leetcode: Arrays Flashcards
Best time to buy a stock
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.
- need to find the current minimum value during the first pass
- as we find values that are lower than our min, which starts at index 0, we change our min to that one
- whenever we find that sell>buy, we do a max calculation
- we can accomplish this in 1 loop because we stop once the right pointer (sell index) is greater than the length of the list. USE FOR LOOP FOR THIS
time: O(n)
space: constant
class BestStockPrice(object):
- —def answer(self, arr):
- ——-buy=0
- ——-money=0
- ——-for i in range(1, len(arr)):
- ———–if arr[i]>arr[buy]:
- —————money=max(money, arr[i]-arr[buy])
- ———–else:
- —————buy=i
- ——-return money
Contains Duplicate
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.
- for loop + set of seen items, if item in set return true, else false
- set() removes duplicates in python. get length of list/set, if len(list)!=len(set), return true (it found a duplicate and removed it) else false
time: linear
space: linear
class ContainsDuplicates(object):
- —def answer(self, arr):
- ——-before=len(arr)
- ——-after=len(set(arr))
- ——-if after!=before:
- ———–return True
- ——-return False
- —def answer2(self, nums):
- ——-seen=set()
- ——-for x in nums:
- ———–if x in seen:
- —————return True
- ———–seen.add(x)
- ——-return False
Murder witnesses
Hi, here’s your problem today. This problem was recently asked by Google:
There are n people lined up, and each have a height represented as an integer. A murder has happened right in front of them, and only people who are taller than everyone in front of them are able to see what has happened. How many witnesses are there?
Example: Input: [3, 6, 3, 4, 1] Output: 3 Explanation: Only [6, 4, 1] were able to see in front of them. -# -# -#-# #### #### ##### 36341----------------------------x (murder scene)
- increment backwards
- update the count each time arr[i] > max
- set the max each time you iterate, if you want 100% optimal you set the new max each time arr[i]>max. This is because if arr[i]> max, then it is the new max
time: O(n)
space: constant
import sys class Solution: ----def answer(self, arr): --------_max=-sys.maxsize-1 --------count=0 --------for i in range(len(arr)-1, -1, -1): ------------if arr[i]>_max: ----------------count+=1 ----------------#_max=max(arr[i], _max) ----------------_max=arr[i] --------return count
Sort list of 3 unique numbers
Hi, here’s your problem today. This problem was recently asked by Google:
Given a list of numbers with only 3 unique numbers (1, 2, 3), sort the list in O(n) time.
Example 1: Input: [3, 3, 2, 1, 3, 2, 1] Output: [1, 1, 2, 2, 3, 3, 3] def sortNums(nums): # Fill this in.
print sortNums([3, 3, 2, 1, 3, 2, 1]) # [1, 1, 2, 2, 3, 3, 3]
- bubble sort, except we know the min/max values so we can make it linear
- need 3 pointers, ones, current, and threes.
- threes decrement when hit, ones/twos increment current, ones increments ones
- check edge cases [1,2,2], [2,2,2]. [1.3.2], [3,3,3]
- threes>=current, we need the equal because if [2,3,1], current=threes but we still need 1 more operation to be correct
time: O(n), we do 1 loop
space: constant, we do not create any additional structures
class Solution:
- —def answer(self, arr):
- ——-threes=len(arr)-1
- ——-current=ones=0
- ——-while threes>=current:
- ———–if arr[current]==1:
- —————arr[ones], arr[current]=arr[current], arr[ones]
- —————ones+=1
- —————current+=1
- ———–elif arr[current]==2:
- —————current+=1
- ———–elif arr[current]==3:
- —————arr[threes],arr[current]=arr[current], arr[threes]
- —————threes-=1
- ——-return arr
Pythagorean triplets
Hi, here’s your problem today. This problem was recently asked by Uber:
Given a list of numbers, find if there exists a pythagorean triplet in that list. A pythagorean triplet is 3 variables a, b, c where a^2 + b^2 = c^2
Example:
Input: [3, 5, 12, 5, 13]
Output: True
Here, 5^2 + 12^2 = 13^2.
brute for is n^3 without making a preprocessed set, probably need to do some square root stuff too
- if you square the list you get the all the possible c^2’s
- make it a set, double for loop to get all the possible a/b combinations
- use set to get constant time searching for c in the list
time: O(n^2), we need to loop twice to see all the values
space: O(n) to store the c^2
class Solution:
- —def answer(self, li):
- ——-squares = {x**2 for x in li}
- ——-for i, x in enumerate(li):
- ———–for y in li[i+1:]:
- —————if x2+y2 in squares:
- ——————-return True
- ——-return False
First and last index of string/number
Hi, here’s your problem today. This problem was recently asked by AirBNB:
Given a sorted array, A, with possibly duplicated elements, find the indices of the first and last occurrences of a target element, x. Return -1 if the target is not found.
# Example: # Input: A = [1,3,3,5,7,8,9,9,9,15], target = 9 # Output: [6,8]
# Input: A = [100, 150, 150, 153], target = 150 # Output: [1,2]
# Input: A = [1,2,3,4,5,6,10], target = 9 # Output: [-1, -1]
brute force is O n, loop until you find, continue until the number isn’t the target
- binary search, understand what binary search is
- this is a variation of it. binary search is usually greater than, less than, or equal to. This combines these depending on if you want the higher index or lower one
- for the lower one, need to prioritize moving to the left if it is equal, on equal but not lowest index move left
- make sure you understand that the stop>=start at all times, if it is not, return -1
- when index==target, make sure that for the right to check if the index+1>current or index==len(list)-1, and do the reverse for the left check. This is for edge checking.
- in this case, you realized after attempting to pass the list[:mid] instead of the start/stop indexes that you would have trouble when figuring out if this was the smallest or largest index of the target. When in doubt, favor the option that gives you more flexibility, hence manage it on your own with start/stop indexes and continue passing the full list in
time: O log(n), binary search
space: O 1, constant space, all work is done in place, no new values stored
class Solution:
- —def answer(self, arr, target):
- ——-low = 0
- ——-high = len(arr)-1
- ——-# last = self.last_index(arr, low, high, target)
- ——-first = self.first_index(arr, low, high, target)
- ——-last = self.last_index(arr, low, high, target)
- ——-return [first, last]
- —def first_index(self, arr, low, high, target):
- ——-if high>=low:
- ———–mid = low+(high-low)//2
- ———–if (mid==0 or target > arr[mid-1]) and arr[mid]==target:
- —————return mid
- ———–elif target <= arr[mid]:
- —————return self.first_index(arr, low, mid-1, target)
- ———–else:
- —————return self.first_index(arr, mid+1, high, target)
- ——-return -1
- —def last_index(self, arr, low, high, target):
- ——-if high>=low:
- ———–mid = (high-low)//2 +low
- ———–if (mid==len(arr)-1 or target=arr[mid]:
- —————return self.last_index(arr, mid+1, high, target)
- ———–else:
- —————return self.last_index(arr, low, mid-1, target)
- ——-return -1
strategies for arrays
SORTED use pointers
binary search if you need to look through a sorted array, binary search can return left which is the first index that is larger than it (or it can return len(N), so check for that)
if asked to list combinations of an item, backtracking
There are more array-related data structures or techniques you might want to know. We will not go deeper into most of the concepts in this card but provide the links to the corresponding card in this article.
- There are some other data structures which are similar to the array but have some different properties:
String (has been introduced in this card)
Hash Table
Linked List
Queue
Stack
2. As we mentioned, we can call the built-in function to sort an array. But it is useful to understand the principle of some widely-used sorting algorithms and their complexity.
- Binary search is also an important technique used to search a specific element in a sorted array.
- We have introduced two-pointer technique in this chapter. It is not easy to use this technique flexibly. This technique can also be used to solve:
Slow-pointer and fast-pointer problem in Linked List
Sliding Window Problem
5. The two-pointer technique sometimes will relate to Greedy Algorithm which helps us design our pointers’ movement strategy.
We will come up with more cards to introduce these techniques mentioned above and update the link in the near future.
Product of Array Except Self
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.
brute force involves a double for loop or using 2 other arrays and doing matrix-type-evaluations on the values before/after the given index.
- write out the solution, with arrays and other problems visualization is key and writing it out helps you solve the issue
- try a for loop that multiplies each number, then one that skips the first number/last number
- loop forward and backward, see what you can find
- once you do that, you should see the forward/backward loop contains the final numbers you want if you do some multiplication, you can then figure out how to multiply to get the answer
[1 2 3 4]
forward=[1 1 2 6 ]
backward=[24 12 4 1]
time: O(2n), we loop twice,
space: contant, the response array does not count
class ProductArrayExceptSelf(object):
- —def answer(self, nums):
- ——-value=1
- ——-response=[]
- ——-for i in range(len(nums)):
- ———–response.append(value)
- ———–value*=nums[i]
- ——-value=1
- ——-for i in range(len(nums)-1, -1, -1):
- ———–response[i]*=value
- ———–value*=nums[i]
- ——-return response
Maximum addition subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
brute is a double for loop that compares max each iteration
- what makes the sum of the entire array less than a subarray? negative numbers
- check max on the current index and current index + current value, if the prev current value was negative we would reset it at the current index
time: linear, O(n)
space: constant
class Solution:
- —def maxSubArray(self, nums: List[int]) -> int:
- ——-response = current = nums[0]
- ——-for i in range(1, len(nums)):
- ———–current = max(nums[i], current + nums[i])
- ———–response = max(current, response)
- ——-return response
BONUS: good to know how to solve a problem this way
time: O( N*log(N)), we loop through once then split into smaller arrays and loop through those. classic NlogN
space: log (n), this is based off the recursive calls, since lh and rh are being calculate at different times, we only ever see log(n) calls on the stack
- —#think merge sort
- —def merge_sort_esque(self, nums, left, right):
- ——-if right [greater than]= left:
- ———–mid = (left+right)//2
- ———–curr=bl=br=0
- ———–for i in range(mid+1, right+1):
- —————curr+=nums[i]
- —————br=max(br, curr)
- ———–curr=0
- ———–for i in range(mid-1, left-1, -1):
- —————curr+=nums[i]
- —————bl=max(bl, curr)
————bc = nums[mid]+bl+br
- ———–lh = self.helper(nums, left, mid-1)
- ———–rh =self.helper(nums, mid+1, right)
- ———–return max(bc, lh, rh)
- ——-else:
- ———–return -float(‘inf’)
max 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.
brute is double for loop with some logic, calculating the max at each iteration. a linear 2 pass solution is to calculate the max going forward/backward.
- —def brute(self, nums):
- ——-m=nums[0]
- ——-for i in range(len(nums)):
- ———–c=1
- ———–for j in range(i, len(nums)):
- —————c*=nums[j]
- —————m=max(c, m)
- ——-return m
- 2 road blocks, 0’s and negative numbers
- 0’s reset the value, but negative numbers do not. if we have an even amount of negatives, then we can multiply everything, but if we have odd, we get a very small number
- we want to keep the max, temp_max (p), and minimum (c). this is because at any point, the min value can become the largest value by multiplying it by another negative
- the hard part is figuring out how to evaluate the min/temp max at each step, we need to do a triple max/min comparison between the current index, CIp, CIc,
- also remember to keep a placeholder temp_max since we use p in both min/max comparisons
- right out this solution, writing out solutions helped me get 75% of the way there, but I messed up bc I didn’t check all edge cases
time: O(n), linear, we do 1 pass
space: constant, we only make new variables
class Solution:
- —def maxProduct(self, nums):
- ——-_max = temp_max = _min = nums[0]
- ——-for i in range(1, len(nums)):
- ———–x = nums[i]
- ———–temp_max, _min = max(x, x_min, temp_maxx) ,min(x, _minx, temp_maxx)
- ———–_max = max(_max, temp_max)
- ——-return _max
pascal’s triangle 2
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
pascals triangle is a triangle where the edges are always 1 and the inner sections are sums of the parts above it
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
- use dynamic programming to build each row, using that row to build the next one
- only keep track of the previous row and the current row
time: O(n^2), we loop through all the row indexes and the lengths of the arrays space O(n^2 + n), since we make an array at each iteration, the space taken up by all the arrays is n^2, the n includes the answer array. I confirmed recursive calls that create arrays are n * height of tree in space, in this case it is n^2
class Solution:
- —def getRow(self, rowIndex):
- ——-return self.helper(rowIndex, [1])
- —def helper(self, ri, p):
- ——-if ri==0:
- ———–return p
- ——-ri-=1
- ——-tp=[0]*(len(p)+1)
- ——-l=len(tp)
- ——-for i in range(l):
- ———–if i==0 or i==l-1:
- —————tp[i]=1
- ———–else:
- —————tp[i]=p[i]+p[i-1]
- ——-return self.helper(ri, tp)
time: O(n^2), we loop through all the row indexes and the lengths of the arrays
space: O(n), linear since we only keep track of the previous array
- —def custom_optimal(self, rowIndex):
- ——-prev, current = deque([1] * (rowIndex + 1)), deque([1] * (rowIndex + 1))
- ——-for i in range(rowIndex + 1):
- ———–for j in range(i):
- —————if j == 0:
- ——————-continue
- —————else:
- ——————-current[j] = prev[j - 1] + prev[j]
- ———–prev, current = current, prev
- ——-return prev
BONUS if you realize you can calculate the next array from the current array, we can even remove the previous array space, making it constant!
- calculate the next row from the previous row. 1 3 3 1, makes 4, 6, 4 1, then we add 1 to the beginning (we can do it reversed too)
- —def optimal(self, rowIndex):
- ——-p = deque([1])
- ——-for i in range(rowIndex):
- ———–for j in range(i):
- —————p[j] = p[j] + p[j+1]
- ———–p.appendleft(1)
- ——-return p
Given an integer numRows, return the first numRows of Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Input: numRows = 1
Output: [[1]]
- know pascal’s triangle
- dynamically build the triangle, start the response with the 0th index of [1] in the response array
- create a new array that is equal to i+1, we don’t need to calculate length bc we know i+1=length of the next array
- careful with indexing and such
time: O(n^2), we have 5, 4, 3, 2, 1, operations, reduces to n^2
space: the response array is a pascal triangle that takes up n^2 space
class Solution:
- —def generate(self, numRows: int):
- ——-response=[[1]]
- ——-for i in range(1, numRows):
- ———–li=[1]*(i+1)
- ———–for j in range(i+1):
- —————if j==0 or j==i:
- ——————-li[j]=1
- —————else:
- ——————-li[j]=response[i-1][j]+response[i-1][j-1]
- ———–response.append(li)
- ——-return response
Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
brute force is to do quick sort/heap sort/any sort, then do len(nums)-k and return that index (7-1 gives 6, which would be the largest in an ascending sorted array)
- quick select
- quicksort but instead of sorting both splits just sort the one where the target>partition or target int
- we also do not have to worry about if high >= low
BONUS: check if high == low, if that is the case array has one element or we have quick selected to the last available element, so it is the answer
time: O(n) average, worst case same as quick sort which is N^2
space: O(log(n)) average, worst case would be O(n). This comes from the recursive calls resulting from a bad pivot
class Solution:
- —def findKthLargest(self, nums, k):
- ——-n = len(nums)
- ——-high = n - 1
- ——-low = 0
- ——-j_smallest = n - k
- ——-return self.quickselect(nums, high, low, j_smallest)
- —def quickselect(self, arr, high, low, j):
- ——-if high == low:
- ———–return arr[low]
- ——-pi = self.partition(arr, high, low)
- ——-if pi == j:
- ———–return arr[j]
- ——-elif pi [less than] j:
- ———–return self.quickselect(arr, high, pi + 1, j)
- ——-else:
- ———–return self.quickselect(arr, pi - 1, low, j)
- —def partition(self, arr, high, low):
- ——-pivot = random.randint(low, high)
- ——-arr[pivot], arr[high] = arr[high], arr[pivot]
- ——-swap = low
- ——-for i in range(low, high):
- ———–if arr[i] [less than] arr[high]:
- —————arr[swap], arr[i] = arr[i], arr[swap]
- —————swap += 1
- ——-arr[swap], arr[high] = arr[high], arr[swap]
- ——-return swap
Combinations
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].
You may return the answer in any order.
easiest way is to use itertools.combinations(iterable, length). get the iterable from range(1, n+1), then loop over the result and append them to the list. (make sure to convert the tuples to lists first)
- backtracking!
- backtracking requires that we are able to undo operations further down the tree
- figure out a way to remove items from a list when you are done with it, pop() is the choice
- when do you pop? after return or after function call? it has to be after the function call, bc if not you will see that it never fully “resets” the temp list. with backtracking, we need to always be able to reset the algo as we go through it
- when appending, make sure you append a deep copy, which is list[:], or else you only pass a reference and will continue to operate on that list within the output
time: O(k*combination count) N!/(k!(n-k)!) is the formula for the number of combinations given options N and length K. appending a list takes K time where k is the length of the list, which is why is has the k
space: O(combination count) which is the space of the final return list. if not counting that, it would be N which is the heigh of the recursion tree
class Solution:
- —def combine(self, n: int, k: int):——–
- ——-self.output=[]
- ——-self.helper(n, k, 1, [])—————-
- ——-return self.output
- —def helper(self, n, k, index, temp):
- ——-if len(temp)==k:
- ———–self.output.append(temp[:])
- ——-else:
- ———–for j in range(index, n+1):
- —————temp.append(j)
- —————self.helper(n, k, j+1, temp)
- —————temp.pop()
- —def using_modules(self, n, k):
- ——-import itertools
- ——-output=[]
- ——-nums=range(1,n+1)
- ——-combos = itertools.combinations(nums, k)
- ——-for c in combos:
- ———–output.append(list(c))
- ——-return output
permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
brute is to use itertools.permutations(iterable, length), returns a list of tuples. conver the tuples to lists and append to output
- backtracking!
- create a set for seen numbers, if seen, skip over them in the loop
- base case is if len(current)==output, then we append that to the output!
time: N!, since it takes N! / (N-K)! to calculate the permutations. N is the values to choose from, K is the size (9 digit keypad, 4 digit code)
space: N!, since that is the output array, recursion depth is N
class Solution:
- —def permute(self, nums: List[int]) -> List[List[int]]:
- ——-output=[]
- ——-self.backtracking(nums, set(), [], output)
- ——-return output
- —def backtracking(self, nums, seen, current, output):
- ——-if len(current)==len(nums):
- ———–output.append(current[:])
- ——-else:
- ———–for x in nums:
- —————if x not in seen:
- ——————-current.append(x)
- ——————-seen.add(x)
- ——————-self.backtracking(nums, seen, current, output)
- ——————-current.pop()
- ——————-seen.remove(x)
- —def permute(self, nums: List[int]) -> List[List[int]]:
- ——-import itertools
- ——-output=[]
- ——-permuations = itertools.permutations(nums, len(nums))
- ——-for x in permuations:
- ———–output.append(list(x))
- ——-return output
Find The Duplicates
Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note that the output array should be sorted in an ascending order.
- equal sizes, think of pointers
- while loop making sure neither pointer is equal to length of respective array
time: O(n+m) since worst case we traverse through both of the arrays fully,
space: is output (constant)
class Solution:
- —def equal_sizes(self, arr1, arr2):
- ——-output=[]
- ——-p1,p2 = 0,0
- ——-while p1[less than]len(arr1) and p2[less than]len(arr2):
- ———–if arr1[p1] is arr2[p2]:
- —————output.append(arr1[p1])
- —————p1+=1
- —————p2+=1
- ———–elif arr1[p1] [less than] arr2[p2]:
- —————p1+=1
- ———–else:
- —————p2+=1
- ——-return output
- duplicates must be in both arrays, so we do a complete loop through the small array and a binary search through the larger array
time: N log(m) where n is smaller and M is larger
space: output array (constant)
- —def not_equal_sizes(self, arr1, arr2):
- ——-if len(arr1)[less than]len(arr2):
- ———–small=arr1
- ———–larger=arr2
- ——-else:
- ———–large=arr1
- ———–small=arr2
- ——-output=[]
- ——-for x in small:
- ———–if self.binary_search(x, large):
- —————output.append(x)
- ——-return output
- —def binary_search(self, target, arr):
- ——-low=0
- ——-high=len(arr)-1
- ——-while high[greater than]=low:
- ———–mid = (high+low)//2
- ———–if arr[mid] is target:
- —————return True
- ———–elif target [less than] arr[mid]:
- —————high=mid-1
- ———–else:
- —————low=mid+1
- ——-return False
Largest rectangle in histograms
Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
brute force would be to do a double for loop, calculating the area based on the minimum value seen since that is the limiting factor of the rectangle area
class Solution:
- —def largestRectangleArea(self, heights):
- ——-output = 0
- ——-for i in range(len(heights)):
- ———–minimum=heights[i]
- ———–for j in range(i, len(heights)):
- —————current = heights[j]
- —————minimum = min(minimum, current)
- —————response = minimum*(j-i+1)
- —————output = max(output, response, current)
- ——-return output
- find the min in the array, min*length = max area for now, then remove the min and divide and conquer!
- Once you get that min, go left and go right, removing that min index, similar to binary search
time: N log N
space: constant
- —def divide_conquer(self, heights):
- ——-output = 0
- ——-for i in range(len(heights)):
- ———–minimum=heights[i]
- ———–for j in range(i, len(heights)):
- —————current = heights[j]
- —————minimum = min(minimum, current)
- —————response = minimum*(j-i+1)
- —————output = max(output, response, current)
- ——-return output
- —def optimal(self, heights):
- ——-stack = [-1]
- ——-max_area = 0
- ——-for i in range(len(heights)):
- ———–while stack[-1] != -1 and heights[stack[-1]] [greater than]= heights[i]:
- —————current_height = heights[stack.pop()]
- —————current_width = i - stack[-1] - 1
- —————max_area = max(max_area, current_height * current_width)
- ———–stack.append(i)
- ——-while stack[-1] != -1:
- ———–current_height = heights[stack.pop()]
- ———–current_width = len(heights) - stack[-1] - 1
- ———–max_area = max(max_area, current_height * current_width)
- ——-return max_area
Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack.
- make sure the append operations keep track of previous min stack values
- make sure that when you pop off values, if that value is the min stack value, you have to account for that by getting a previous stack value
- make sure that you account for numbers of equal value being added to the stack, this is important for the min stack values
time: everything is linear
space: the stack itself is N, the min_stack could be N space too worst case
class MinStack:
- —def __init__(self):
- ——-self.stack = []
- ——-self.min_stack = []
- —def push(self, val: int) -[greater than] None:
- ——-if not self.min_stack or val [less than]= self.min_stack[-1]:
- ———–self.min_stack.append(val)
- ——-self.stack.append(val)
- —def pop(self) -[greater than] None:
- ——-val = self.stack.pop()
- ——-if val == self.min_stack[-1]:
- ———–self.min_stack.pop()
- —def top(self) -[greater than] int:
- ——-if len(self.stack) [greater than] 0:
- ——-else:
- ———–return None
- —def getMin(self) -[greater than] int:
- ——-if len(self.min_stack) [greater than] 0:
- ———–return self.min_stack[-1]
- ——-else:
- ———–return None
find pivot index
Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index’s right.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.
Example 1:
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11
brute force could be a 2 pointer, calculate sum on each side of inner-loop, return if true
I tried a 2-pointer solution, but there are too many edge cases with negative numbers that make a left/right sum with pointers extremely difficult
- calculate sum of array
- iterate through array and add values to left. When we find sum - left - current == left, we found the pivot!
time: O(N)
space: constant
class Solution:
- —def pivotIndex(self, nums):
- ——-if len(nums) == 0:
- ———–return -1
- ——-total = sum(nums)
- ——-left = 0
- ——-for i in range(len(nums)):
- ———–if left == (total - left - nums[i]):
- —————return i
- ———–else:
- —————left += nums[i]
- ——-return -1
