30 Most Important Array Interview Questions
with Python Code
1. Two Sum
def twoSum(nums,target):
d={}
for i,x in enumerate(nums):
if target-x in d:return [d[target-x],i]
d[x]=i
2. Best Time to Buy and Sell Stock
def maxProfit(p):
m=p[0];a=0
for x in p:
m=min(m,x);a=max(a,x-m)
return a
3. Maximum Subarray
def maxSubArray(a):
c=m=a[0]
for x in a[1:]:
c=max(x,c+x);m=max(m,c)
return m
4. Merge Sorted Array
def merge(a,m,b,n):
a[m:]=b
[Link]()
5. Move Zeroes
def moveZeroes(a):
j=0
for i in range(len(a)):
if a[i]!=0:a[j],a[i]=a[i],a[j];j+=1
6. Rotate Array
def rotate(a,k):
k%=len(a);a[:]=a[-k:]+a[:-k]
7. Remove Duplicates
def removeDuplicates(a):
j=1
for i in range(1,len(a)):
if a[i]!=a[i-1]:a[j]=a[i];j+=1
return j
8. Product Except Self
def productExceptSelf(a):
n=len(a);r=[1]*n;p=1
for i in range(n):r[i]=p;p*=a[i]
s=1
for i in range(n-1,-1,-1):r[i]*=s;s*=a[i]
return r
9. Majority Element
def majorityElement(a):
c=0;v=None
for x in a:
if c==0:v=x
c+=1 if x==v else -1
return v
10. Missing Number
def missingNumber(a):
n=len(a);return n*(n+1)//2-sum(a)
11. Contains Duplicate
def containsDuplicate(a):
return len(a)!=len(set(a))
12. Single Number
from functools import reduce
from operator import xor
def singleNumber(a):
return reduce(xor,a)
13. Intersection of Arrays
def intersect(a,b):
return list(set(a)&set;(b))
14. Plus One
def plusOne(d):
n=int(''.join(map(str,d)))+1
return list(map(int,str(n)))
15. Find Duplicate
def findDuplicate(a):
return next(x for x in a if [Link](x)>1)
16. Sort Colors
def sortColors(a):
[Link]()
17. Third Maximum
def thirdMax(a):
s=sorted(set(a),reverse=True)
return s[2] if len(s)>2 else s[0]
18. Find Peak Element
def findPeak(a):
return [Link](max(a))
19. Max Consecutive Ones
def findMaxConsecutiveOnes(a):
c=m=0
for x in a:
c=c+1 if x else 0;m=max(m,c)
return m
20. Find Disappeared Numbers
def findDisappearedNumbers(a):
return list(set(range(1,len(a)+1))-set(a))
21. Merge Intervals
def mergeIntervals(iv):
[Link]();r=[]
for s,e in iv:
if not r or r[-1][1] else:r[-1][1]=max(r[-1][1],e)
return r
22. Spiral Matrix
def spiralOrder(m):
r=[]
while m:r+=[Link](0);m=list(zip(*m))[::-1]
return r
23. Container With Most Water
def maxArea(h):
l,r=0,len(h)-1;a=0
while l a=max(a,min(h[l],h[r])*(r-l));
l+=h[l]=h[r]
return a
24. Trapping Rain Water
def trap(h):
l,r=0,len(h)-1;lm=rm=0;a=0
while l if h[l] else:rm=max(rm,h[r]);a+=rm-h[r];r-=1
return a
25. Kth Largest
import heapq
def findKthLargest(a,k):
return [Link](k,a)[-1]
26. Subarray Sum Equals K
def subarraySum(a,k):
d={0:1};s=c=0
for x in a:
s+=x;c+=[Link](s-k,0);d[s]=[Link](s,0)+1
return c
27. Maximum Product Subarray
def maxProduct(a):
mx=mn=ans=a[0]
for x in a[1:]:
if x<0:mx,mn=mn,mx
mx=max(x,mx*x);mn=min(x,mn*x);ans=max(ans,mx)
return ans
28. Find Minimum Rotated
def findMin(a):
return min(a)
29. Search Rotated Array
def search(a,t):
return [Link](t) if t in a else -1
30. Longest Consecutive Sequence
def longestConsecutive(a):
s=set(a);ans=0
for x in s:
if x-1 not in s:
y=x
while y in s:y+=1
ans=max(ans,y-x)
return ans