Array problems on LeetCode
1 Linked List Introduction
Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.
Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have following limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.
Advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion
Drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
For Linked List, we can only iterate over elements, for python code example:
#Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None#First, construct a head and point and record the head
pointer=head = ListNode(None)
#loop through all node
while pointer:
print pointer.val
pointer = pointer.next
Dummy Node in Linked List
- Remove Duplicates from Sorted List II
- Reverse Linked List II
- Partition List
Basic Linked List Skills
- Sort List
- Reorder List
Two Pointers in Linked List (Fast-slow pointers)
- Merge K Sorted Lists
2. Summary
Here array means one dimension list. For array problems, math will play an important role here. For this type of question, it is hard to generalize the types, but I will try my best.
- Easy problems: Duplicates: 217, 26, 27, 219, 287, 442; Intersection: 349. Intersection of Two Arrays; Consecutive: 485. Max Consecutive Ones
- Maximum/Minimum subarray: 718, 53. Maximum Subarray, 325. Maximum Size Subarray Sum Equals k. 209. Minimum Size Subarray Sum Solutions: divide and conquer, special sum and hashtable, two pointers (sliding window) for minimum
- Sum of K numbers of elements: Target, return either the index or the elements(might need to avoid repetition). (2/3/4 sums)
- Partition a list into K equal part: DP
3. Steps to Resolve the Problems
For simple questions, basic math and data structure can solve the problems. For more difficult problems:
(1) Analyze the problem, if the sorting algorithm is needed. (nlogn)
(2) Solve the problem in the draft paper. (Brute force, or other algorithms that can be used)
Note: If the problem is complex, trying to see the simple version, and then upgrade the simple version to a complex one. e.g. (487. Max Consecutive Ones II, 485. Max Consecutive Ones)
(3) Check the special case. (Usually very important for this type of problems)
4. Related Algorithms
Flexible Two pointers
T1: If you see in the problem that you can do comparison and it is always one type of satisfactory element is in ahead of the other, this could be resolved by two pointers (slower and faster). Note: when the while loop stops, is there operations you need?
Two pointers is a superset of the sliding window algorithm, prefix sum too.
T2: Or one starts from the beginning, one from the end and going to the middle (sliding window).
Prefix Sum
For the problems that need to sum up subarray, sum(i,j)=sum(0,j)-sum(0,i).
If we want the sum==k, sum(j,i)=sum(0,i)-sum(0,j) =k, when i=1, j=0. so for the loop, index i-> sum[i+1]. we save prefix sum, at the same time, we check if we can find a sum(0,j) ==sum(0,i)-k, j locates in front of index i, and from j to i would have sum k. For a lot of subarray problems, we just need to differentiate the dict[sum_i]=**.
Examples: 122. Best Time to Buy and Sell Stock II (multiple transaction, accumulate sectional profit), 26, 27, 283. Move Zeroes, 121. Best Time to Buy and Sell Stock (keep track of min_price and max_profit, single pass, one transaction), 88. Merge Sorted Array, 167. Two Sum II — Input array is sorted(t2), 11. Container With Most Water (t2, move with greedy programming)
Merge Lists
We can use divide and conquer (see the merge sort) and the priority queue.
Floyd’s Cycle-Finding Algorithm:
Without this we detect cycle with the following code:
def detectCycle(self, A):
visited=set()
head=point=A
while point:
if point.val in visited:
return point
visited.add(point)
point=point.next
return NoneTraverse linked list using two pointers. Move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop. Once you detect a cycle, think about finding the starting point.
def detectCycle(self, A):
#find the "intersection"
p_f=p_s=A
while (p_f and p_s and p_f.next):
p_f = p_f.next.next
p_s = p_s.next
if p_f==p_s:
break
#Find the "entrance" to the cycle.
ptr1 = A
ptr2 = p_s;
while ptr1 and ptr2:
if ptr1!=ptr2:
ptr1 = ptr1.next
ptr2 = ptr2.next
else:
return ptr1
return NoneIntersections: 349. Intersection of Two Arrays
Hashset:
268. Missing Number
DP:
39. Combination Sum, 416. Partition Equal Subset Sum, 698. Partition to K Equal Sum Subsets
LCS:
718. Maximum Length of Repeated Subarray
Kadane’s Algorithm:
O(n) vs brute force O(N²)
Initialize:
max_so_far = -maxint
max_ending_here = 0for i in xrange(len(a)):
(a) max_ending_here = max_ending_here + a[i](b) if( max_ending_here > max_so_far) #update the max
max_so_far = max_ending_here
(c) if(max_ending_here < 0) # discard the values before
max_ending_here = 0return max_so_far
4 Examples
4.1 Sum
In this section, to get sum we can choose to use hashmap to save the original list so that for the last element, we only check the hashmap, we can lower the complexity by one power of n. However, a better solution is to use two pointers or three pointers. for three pointers, the first one is to make sure the starting point. Also, we can think about divide and conquer.
[-4,-1,-1,0,1,2]
i, l-> ``````<-r
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Solution: Should use three pointers, no extra space. i is the start point from [0,len-2], l,r is the other two pointers. l=i+1, r=len-1 at the beignning. The saving of time complexity is totally from the sorting algorithm.
[-4,-1,-1,0,1,2]
i, l-> ``````<-r
How to delete repeat?
def threeSum(self, nums):
res = []
nums.sort()
for i in xrange(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]: #make sure pointer not repeat
continue
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l +=1
elif s > 0:
r -= 1
else:
res.append((nums[i], nums[l], nums[r]))
l+=1
r-=1 #after the first run, then check duplicate example.
while l < r and nums[l] == nums[l-1]:
l += 1
while l < r and nums[r] == nums[r+1]:
r -= 1
return res
Use hashmap:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res =[]
nums=sorted(nums)
if not nums:
return []
if nums[-1]<0 or nums[0]>0:
return []
end_position = len(nums)-2
dic_nums={}
for i in xrange(1,len(nums)):
dic_nums[nums[i]]=i# same result save the last index
for i in xrange(end_position):
target = 0-nums[i]
if i>0 and nums[i] == nums[i-1]: #this is to avoid repeat
continue
if target<nums[i]: #if the target is smaller than this, we can not find them on the right side
break
for j in range(i+1,len(nums)): #this is to avoid repeat
if j>i+1 and nums[j]==nums[j-1]:
continue
complement =target - nums[j]
if complement<nums[j]: #if the left numbers are bigger than the complement, no need to keep searching
break
if complement in dic_nums and dic_nums[complement]>j: #need to make sure the complement is bigger than nums[j]
res.append([nums[i],nums[j],complement])
return resThe following code uses more time
for i in xrange(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
if l-1>=i+1 and nums[l] == nums[l-1]: #check the front
l += 1
continue
if r+1<len(nums) and nums[r] == nums[r+1]:
r -= 1
continue
s = nums[i] + nums[l] + nums[r]
if s < 0:
l +=1
elif s > 0:
r -= 1
else:
res.append((nums[i], nums[l], nums[r]))
l += 1; r -= 1
return resdef fourSum(self, nums, target):
def findNsum(nums, target, N, result, results):
if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N: # early termination
return
if N == 2: # two pointers solve sorted 2-sum problem
l,r = 0,len(nums)-1
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
r-=1
while l < r and nums[l] == nums[l-1]:
l += 1
while l < r and nums[r] == nums[r+1]:
r -= 1
elif s < target:
l += 1
else:
r -= 1
else: # recursively reduce N
for i in range(len(nums)-N+1):
if i == 0 or (i > 0 and nums[i-1] != nums[i]):
findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results) #reduce nums size, reduce target, save resultresults = []
findNsum(sorted(nums), target, 4, [], results)
return results
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228–1 and the result is guaranteed to be at most 231–1.
Example:
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]Output:
2Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
Solution: if we use brute force, use 4 for loop, then it is O(N⁴). If we use divide and conquer, sum the first half, and save a dictionary (counter), time complexity is O(2N²). What if we have 6 sum, we can reduce it to O(2N³), what if 8 sum.
def fourSumCount(self, A, B, C, D):
AB = collections.Counter(a+b for a in A for b in B)
return sum(AB[-c-d] for c in C for d in D)4.2 Subarray 20/670
In this section, we have maximum subarray and minimum subarray. For the maximum, we can use math and prefix_sum, for the minimum subarray, we use sliding window solution. For subarray the most important feature is contiguous. Here, we definitely will not use sorting.
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
Solution: Brute force is to use two for loops, first is the starting, second is the end, then we can get the maximum value. To optimize, we can use divide and conquer, O(nlgn) vs brute force is O(N²)
from sys import maxint
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def getCrossMax(low,mid,high):
left_sum,right_sum =0,0
left_max, right_max = -maxint, -maxint
left_i,right_j=-1,-1
for i in xrange(mid,low-1,-1): #[)
left_sum+=nums[i]
if left_sum>left_max:
left_max= left_sum
left_i = i
for j in xrange(mid+1,high+1):
right_sum+=nums[j]
if right_sum>right_max:
right_max= right_sum
right_j = j
return (left_i,right_j,left_max+right_max)
def maxSubarray(low,high):
if low==high:
return (low,high, nums[low])
mid = (low+high)//2
rslt=[]
#left_low, left_high, left_sum = maxSubarray(low,mid) #[low,mid]
rslt.append(maxSubarray(low,mid)) #[low,mid]
#right_low,right_high,right_sum = maxSubarray(mid+1,high)#[mid+1,high]
rslt.append(maxSubarray(mid+1,high))
#cross_low,cross_high,cross_sum = getCrossMax(low, mid, high)
rslt.append(getCrossMax(low, mid, high))
return max(rslt, key=lambda x: x[2])
return maxSubarray(0,len(nums)-1)[2]2: BCR, O(N)
from sys import maxint
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_so_far = -maxint - 1
max_ending_here = 0
for i in range(0, len(nums)):
max_ending_here = max_ending_here + nums[i]
if (max_so_far < max_ending_here):
max_so_far = max_ending_here
if max_ending_here < 0:
max_ending_here = 0
return max_so_far325. Maximum Size Subarray Sum Equals k
Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.
Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
Example 1:
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)
Example 2:
Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)
Follow Up:
Can you do it in O(n) time?
Solution: using prefix_sum and hashmap, to just need to reformulate dict[sum_i]. For this question, we need to get the maximum size of subarray, so dict[i] =min(idx), the earliest that the value appear. which means every time we just set the dict[i]=current_idx,only if the key doesnt exist. dict[0]=-1. Here we have sum_i, to check if there is a j in front of i that makes sum(j,i)=k, sum(j,i)=sum_i-A Value in Dict = k, so the value need to be sum_i-k, so that we need to check if it is in the dictionary.
def maxSubArrayLen(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
sum_i = 0
dict = {0:-1} #this means for index -1, the sum is 0
max_len = 0
for idx,v in enumerate(nums):
sum_i+=v
if sum_i not in dict:
dict[sum_i] = idx
if sum_i-k in dict:
max_len=max(max_len, idx-dict[sum_i-k])
return max_lenGiven an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2Solution 2: Python with LTE error
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
''' return the number of subarrays that equal to k'''
count = 0
sums=[0]*(len(nums)+1)
for idx, v in enumerate(nums):
sums[idx+1]=sums[idx]+v
for i in range(len(nums)):
for j in range(i, len(nums)):
value = sums[j+1]-sums[i]
count=count+1 if value==k else count
return countSolution 3: using prefix_sum and hashmap, to just need to reformulate dict[sum_i]. For this question, we need to get the total number of subsubarray, so dict[i] =count, which means every time we just set the dict[i]+=1. dict[0]=1
import collections
class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
''' return the number of subarrays that equal to k'''
dict = collections.defaultdict(int) #the value is the number of the sum occurs
dict[0]=1
current_sum, count=0, 0
for v in nums:
current_sum+=v
count+=dict[current_sum-k]
dict[current_sum]+=1
return countGiven a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.Note: The length of the given binary array will not exceed 50,000.
Solution: the problem is similar to the maximum sum of array with sum==0, so 0=-1, 1==1.
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums=[nums[i] if nums[i]==1 else -1 for i in range(len(nums))]
max_len=0
cur_sum=0
mapp={0:-1}
for idx,v in enumerate(nums):
cur_sum+=v
if cur_sum in mapp:
max_len=max(max_len,idx-mapp[cur_sum])
else:
mapp[cur_sum]=idx
return max_len209. Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
i,j=0,0
sum=0
min_length=len(nums)+1
while j<len(nums):
sum+=nums[j]
j+=1
#shrink the sliding window size
while sum>=s and i<len(nums):
min_length=min(min_length, j-i)
sum-=nums[i] #shrink
i+=1
return min_length if min_length< len(nums)+1 else 0152 (product)
For the product: we need to record the min_ending_here, for the max_ending_here, can only be [1, +infinity), min_ending_here (-infinity, 1]
Initialize:
max_so_far = -maxint
max_ending_here = 1
min_ending_here = 1for i in xrange(len(a)):
(a) if a[i]>=0 # keep the same
max_ending_here = max_ending_here *a[i]
min_ending_here = min(min_ending_here *a[i], 1)
max_so_far = max(max_ending_here,max_so_far)
if nums[i]==0:
max_ending_here = 1
min_ending_here = 1
(b) else: #negative, then max and the min is going to be changed
max_so_far = max(min_ending_here * nums[i], max_so_far)
#exchange the max_ending here and the min_ending_here
temp = max_ending_here
max_ending_here = max (min_ending_here * nums[i], 1)
min_ending_here = temp * nums[i] # mini change to be negative againreturn max_so_far
674. Longest Continuous Increasing Subsequence
Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).
Example 1:
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.Example 2:
Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.Note: Length of the array will not exceed 10,000.
Solution: The brute force solution is use two for loops with O(n²). The first loop is the start number, the second loop is the nums[j]>nums[j-1] or else stop. Or we can use two pointers. i,j start from 0,1 respectively.
class Solution:
def findLengthOfLCIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
if len(nums)==1:
return 1
i,j=0,1
max_length = 0
while j<len(nums):
if nums[j-1]<nums[j]:
j+=1
else:
if j-i>max_length:
max_length = j-i
i=j
j+=1
if j-i>max_length:
max_length = j-i
return max_length300. Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n^2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Solution: Compared with the last question, this one loose the restriction that need to be continuous. For this problem, we need to understand it is not going to work with two for loops. It is not a brute-force O(n²) problem. It is a typical combination problem in recursive functions. So, at first, put the standard combination algorithm code here:
def dfs(temp, idx):
rslt.append(temp[:]) #pass temp[:] with shollow copy so that we wont change the result of rslt when temp is changed
for i in range(idx, len(nums)):
temp.append(nums[i])
#backtrack
dfs(temp, i+1)
temp.pop()
dfs([],0)
return rsltSo, we use the backtracking — combination to enumerate all possible subsequence. The difference is here we do not unconditionally use this nums[i] in our result, only if nums[i]>tail, and the final length is the maximum of them all. T(n) = max(T(n-1)+1, T(n-k)+1, …). So, the time complexity is O(2^n). It passed 21/15 test cases with TLE. In this process, we transfer from the combination problem to dynamic programming.
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_count = 0
if not nums:
return 0
def backtrackingDFS(idx,tail):
if idx==len(nums):
return 0
length = 0
for i in range(idx,len(nums)):
if nums[i]>tail:
length = max(1+backtrackingDFS(i+1, nums[i]), length)
return length
return backtrackingDFS(0,-maxsize)Now, we know we are doing dynamic programming, if we already know the ans(idx), meaning the max length from somewhere, we do not need to do it again. With memoization: The time complexity is n subproblem, top-down recursive+memo.
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_count = 0
if not nums:
return 0
memo =[None for _ in range(len(nums))]
def backtrackingDFS(idx,tail):
if idx==len(nums):
return 0
if memo[idx]==None:
length = 0
for i in range(idx,len(nums)):
if nums[i]>tail:
length = max(1+backtrackingDFS(i+1, nums[i]), length)
memo[idx]=length
return memo[idx]
return backtrackingDFS(0,-maxsize)Now, we use dp and bottom-up iterative. For [10,9,2,5,3], the length array is [1,1,1,2,2], for [4,10,4,3,8,9], we have [1, 2, 1, 1, 2, 3]. To find the rule, T(0)=1, idx, max(memo[i]),0≤i<idx, nums[idx]>nums[i]. Now the time complexity is O(n²).
state: f[i] record the maximum length of increasing subsequence from 0-i.
function: f[i]: choose or not to choose
initialize: f[0]=1
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_count = 0
if not nums:
return 0
dp=[0 for _ in range(len(nums))]
dp[0]=1
maxans =1
for idx in range(1,len(nums)): #current combine this to this subsequence, 10 to [], 9 to [10]
pre_max=0
for i in range(0,idx):
if nums[idx]>nums[i]:
pre_max=max(pre_max, dp[i])
dp[idx]=pre_max+1
maxans=max(maxans,dp[idx])
print(dp)
return maxansWe can even speedup further by using binary search, the second loop we can use a binary search to make the time complexity O(logn), and the dp array used to save the maximum ans. Each time we use binary search to find an insertion point, if it is at the end, then the length grow.
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def binarySearch(arr,l,r,num):
while l<r:
mid = l+(r-l)//2
if num>arr[mid]:
l=mid+1
elif num<arr[mid]:
r=mid
else:
return mid
return l
max_count = 0
if not nums:
return 0
dp =[0 for _ in range(len(nums))]#save the maximum till now
maxans =1
length=0
for idx in range(0,len(nums)): #current combine this to this subsequence, 10 to [], 9 to [10]
pos = binarySearch(dp,0,length,nums[idx]) #find insertion point
dp[pos]= nums[idx] #however if it is not at end, we replace it, current number
if pos==length:
length+=1
print(dp)
return length673. Number of Longest Increasing Subsequence
Given an unsorted array of integers, find the number of longest increasing subsequence.
Example 1:
Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].Example 2:
Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.
Solution: Another different problem, to count the number of the max subsequence. Typical dp:
state: f[i]
from sys import maxsize
class Solution:
def findNumberOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_count = 0
if not nums:
return 0
memo =[None for _ in range(len(nums))]
rlst=[]
def recursive(idx,tail,res):
if idx==len(nums):
rlst.append(res)
return 0
if memo[idx]==None:
length = 0
if nums[idx]>tail:
addLen = 1+recursive(idx+1, nums[idx],res+[nums[idx]])
notAddLen = recursive(idx+1, tail,res)
return max(addLen,notAddLen)
else:
return recursive(idx+1, tail,res)
ans=recursive(0,-maxsize,[])
count=0
for lst in rlst:
if len(lst)==ans:
count+=1
return countUsing dynamic programming, the difference is we add a count array.
from sys import maxsize
class Solution:
def findNumberOfLIS(self, nums):
N = len(nums)
if N <= 1: return N
lengths = [0] * N #lengths[i] = longest ending in nums[i]
counts = [1] * N #count[i] = number of longest ending in nums[i]for idx, num in enumerate(nums): #i
for i in range(idx): #j
if nums[i] < nums[idx]: #bigger
if lengths[i] >= lengths[idx]:
lengths[idx] = 1 + lengths[i] #set the biggest length
counts[idx] = counts[i] #change the count
elif lengths[i] + 1 == lengths[idx]: #if it is a tie
counts[idx] += counts[i] #increase the current count by count[i]longest = max(lengths)
print(counts)
print(lengths)
return sum(c for i, c in enumerate(counts) if lengths[i] == longest)
128. Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
Solution: Not thinking about the O(n) complexity, we can use sorting to get [1,2,3,4,100,200], and then use two pointers to get [1,2,3,4].
How about O(n)? We can pop out a number in the list, example, 4 , then we use while first-1 to get any number that is on the left side of 4, here it is 3, 2, 1, and use another to find all the bigger one and remove these numbers from the nums array.
def longestConsecutive(self, nums):
nums = set(nums)
maxlen = 0
while nums:
first = last = nums.pop()
while first - 1 in nums: #keep finding the smaller one
first -= 1
nums.remove(first)
while last + 1 in nums: #keep finding the larger one
last += 1
nums.remove(last)
maxlen = max(maxlen, last - first + 1)
return maxlen594. Longest Harmonious Subsequence
We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.
Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.
Example 1:
Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].Note: The length of the input array will not exceed 20,000.
Solution: at first, use a Counter to save the whole set. Then visit the counter dictionary, to check key+1 and key-1, only when the item is not zero, we can count it as validate, or else it is 0.
from collections import Counter
class Solution:
def findLHS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums or len(nums)<2:
return 0
count=Counter(nums) #the list is sorted by the key value
maxLen = 0
for key,item in count.items(): #to visit the key: item in the counter
if count[key+1]: #because the list is sorted, so we only need to check key+1
maxLen = max(maxLen,item+count[key+1])
# if count[key-1]:
# maxLen=max(maxLen, item+count[key-1])
return maxLen521. Longest Uncommon Subsequence I
Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.
A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.
The input will be two strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1.
Example 1:
Input: "aba", "cdc"
Output: 3
Explanation: The longest uncommon subsequence is "aba" (or "cdc"),
because "aba" is a subsequence of "aba",
but not a subsequence of any other strings in the group of two strings.Note:
- Both strings’ lengths will not exceed 100.
- Only letters from a ~ z will appear in input strings.
Solution: if we get more examples, we could found the following rules, “aba”,”aba” return -1,
def findLUSlength(self, a, b):
"""
:type a: str
:type b: str
:rtype: int
"""
if len(b)!=len(a):
return max(len(a),len(b))
#length is the same
return len(a) if a!=b else -1424. Longest Repeating Character Replacement
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.
Note:
Both the string’s length and k will not exceed 104.
Example 1:
Input:
s = "ABAB", k = 2Output:
4Explanation:
Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input:
s = "AABABBA", k = 1Output:
4Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
Solution: the brute-force recursive solution for this, is try to replace any char into another when it is not equal or choose not too. LTE
#brute force, use recursive function to write brute force solution
def replace(news, idx, re_char, k):
nonlocal maxLen
if k==0 or idx==len(s):
maxLen = max(maxLen, getLen(news))
returnif s[idx]!=re_char: #replace
news_copy=news[:idx]+re_char+news[idx+1:]
replace(news_copy, idx+1, re_char, k-1)
replace(news[:], idx+1, re_char,k)
#what if we only have one char
# for char1 in chars.keys():
# replace(s[:],0,char1, k)
To get the BCR, think about the sliding window. The longest repeating string we can by number of replacement = `length of string — max(numer of occurence of letter i), i=’A’ to ‘Z’. With the constraint, which means the equation needs to be ≤ k. So we can use sliding window to record the max occurence, and when the constraint is violated, we shrink the window. Given an example, strs= “BBCABBBAB”, k=2, when i=0, and j=7, 8–5=3>2, which is at A, we need to shrink it, the maxCharCount changed to 4, i=1, so that 8–1–4=3, i=2, 8–2–3=3, 8–3–3=2, so i=3, current length is 5.
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
i,j = 0,0 #sliding window
counter=[0]*26
ans = 0
maxCharCount = 0
while j<len(s):
counter[ord(s[j])-ord('A')]+=1
maxCharCount = max(maxCharCount, counter[ord(s[j])-ord('A')])
while j-i+1-maxCharCount>k: #now shrink the window
counter[ord(s[i])-ord('A')]-=1
i+=1
#updata max
maxCharCount=max(counter)
ans=max(ans, j-i+1)
j+=1
return ans395. Longest Substring with At Least K Repeating Characters
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input:
s = "aaabb", k = 3Output:
3The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input:
s = "ababbc", k = 2Output:
5The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
Solution: use dynamic programming with memo: Cons: it takes too much space, and with LTE.
from collections import Counter, defaultdict
class Solution:
def longestSubstring(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
if not s:
return 0
if len(s)<k:
return 0
count = Counter(char for char in s)
print(count)
memo=[[None for col in range(len(s))] for row in range(len(s))]def cut(start,end,count):
if start>end:
return 0
if memo[start][end]==None:
if any(0<item<k for key,item in count.items()):
newCounterF=count.copy()
newCounterF[s[start]]-=1
newCounterB=count.copy()
newCounterB[s[end]]-=1
#print(newsF,newsB)
memo[start][end]= max(cut(start+1, end, newCounterF), cut(start, end-1, newCounterB))
else:
memo[start][end] = end-start+1
return memo[start][end]
return cut(0,len(s)-1,count)
Now, use sliding window, we use a pointer mid, what start from 0, if the whole string satisfy the condition, return len(s). Otherwise, use two while loop to separate the string into three substrings: left, mid, right. left satisfy, mid unsatisfy, right unknown.
from collections import Counter, defaultdict
class Solution:
def longestSubstring(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
if not s:
return 0
if len(s)<k:
return 0
count = Counter(char for char in s)
mid=0 #on the left side, from 0-mid, satisfied elments
while mid<len(s) and count[s[mid]]>=k:
mid+=1
if mid==len(s): return len(s)
left = self.longestSubstring(s[:mid],k) #"ababb"
#from pre_mid - cur_mid, get rid of those cant satisfy the condition
while mid<len(s) and count[s[mid]]<k:
mid+=1
#now the right side keep doing it
right = self.longestSubstring(s[mid:],k)
return max(left,right)720. Longest Word in Dictionary
Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.
If there is no answer, return the empty string.
Example 1:
Input:
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation:
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".Example 2:
Input:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation:
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smallerSolution: Sort the words and then save a set of it to check the parent of it.
import functools
class Solution:
def longestWord(self, words):
"""
:type words: List[str]
:rtype: str
"""
#write a compare function
def cmp(x,y):
if len(x)>len(y):
return 1
elif len(x)<len(y):
return -1
else:
if x<y: #when there is a tie, when want the smaller on at first
return 1
elif x>y:
return -1
else:
return 0
words=sorted(words,key=functools.cmp_to_key(cmp), reverse=True)
print(words)
dict1=set(words)
#Now look for all the parents see if they are inside
for word in words:
par = word[:-1]
while par in dict1:
par=par[:-1]
if par=='':
return word4.3 Combination
Recursive (DFS and BFS), divide and conquer (divide into subproblems)
curr: used to record current chosen elements. (curr.push, pop())
[2, 3, 6, 7] and target 7, A solution set is:
[
[7],
[2, 2, 3]
]Solution: For this combination, we can use each element one to all possible number of times. We recursively try call possible. The set is like a graph, at the beiginning, we start from 2, the next 3,6,7 are adjacent. Then for 3, nodes 6,7 are its possible next steps. T(n) =kT(n-1)
2
2 3 6 7
The python code:
def combinationSum(self, candidates, target):
res = []
candidates.sort()
self.dfs(candidates, target, 0, [], res)
return res
def dfs(self, nums, target, index, path, res):
if target < 0:
return # backtracking
if target == 0:
res.append(path)
return
for i in xrange(index, len(nums)):
self.dfs(nums, target-nums[i], i, path+[nums[i]], res) #path+[nums[i]]416. Partition Equal Subset Sum
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
- Each of the array element will not exceed 100.
- The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]Output: trueExplanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]Output: falseExplanation: The array cannot be partitioned into equal sum subsets.
Solution, for this problem we just need to find see if any of the subproblems return true. So, it is important to use any()
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if not nums:
return False
s = sum(nums)
if s%2:
return False memo={}
def isSubsetSum(s,e, r): #r is the remaining target
if r==0:
return True
if r<0:
return False
if r not in memo:
memo[r] = any(isSubsetSum(i+1,e,r-nums[i]) for i in xrange(s,e))
return memo[r]
return isSubsetSum(0,len(nums)-1,s//2)
Solution2: dp, 背包问题
698. Partition to K Equal Sum Subsets
Solution 1: we have k groups, each time we try to deal with one element from nums, see which group we should put them inside. Then we try to put them in any group that might fit in. Time Complexity: O(kN−kk!)O(k^{N-k} k!)O(kN−kk!), where NNN is the length of nums, and kkk is as given. As we skip additional zeroes in groups, naively we will make O(k!)O(k!)O(k!) calls to search, then an additional O(kN−k)O(k^{N-k})O(kN−k) calls after every element of groups is nonzero. Space Complexity: O(N)O(N)O(N), the space used by recursive calls to search in our call stack. More solutions.
def canPartitionKSubsets(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if not nums:
return False
s = sum(nums)
if s%k:
return False
target=s/k
memo={}
def isSubsetSum(groups): #r is the remaining target
if not nums:
return True
v=nums.pop() #pop 4
for idx,pre_sum in enumerate(groups):
if pre_sum+v<=target:
groups[idx]+=v
if isSubsetSum(groups):
return True
groups[idx]-=v
print(pre_sum)
if not pre_sum: break # One important speedup is that we can ensure all the 0 values of each group occur at the end of the array groups, by enforcing if (groups[i] == 0) break;. This greatly reduces repeated work - for example, in the first run of search, we will make only 1 recursive call, instead of k. Actually, we could do better by skipping any repeated values of groups[i], but it isn't necessary.
#didnt work out, revover the nums
nums.append(v)
return False
nums.sort() #sort from small to big
if nums[-1] > target: return False
while nums and nums[-1] == target:
nums.pop()
k -= 1return isSubsetSum([0] * k)
4.4 Merge Lists
23. Merge k Sorted Lists, 21. Merge Two Sorted Lists
Brute force is to get all the element values in a list, sort it and build a LinkedList. Others could be divide and conquer. O(nlogk)
from Queue import PriorityQueue
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
head = point = ListNode(0)
q = PriorityQueue()
for l in lists:
if l:
q.put((l.val, l))
while not q.empty():
val, node = q.get()
point.next = node
point = point.next
node = node.next
if node:
q.put((node.val, node))
return head.nextAppendix
Python Set; Python List; Python list copy: this is very important, especially if we need to copy a two dimensional list or even higher, use deepcopy() from copy module.
Python set min or max’s initial value:
from sys import maxint
max_value = -maxint-1
min_value = maxint#float
float_max_value = float('-inf')
float_min_value = float('inf')
For example: 784. Letter Case Permutation
Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.
Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]Input: S = "3z4"
Output: ["3z4", "3Z4"]Input: S = "12345"
Output: ["12345"]
Solution:
import copy
class Solution(object):
def letterCasePermutation(self, S):
"""
:type S: str
:rtype: List[str]
"""
if not S:
return [""]
r=[]
for c in S:
if c.isalpha():
#split the original into more
if not r:
r.append([c.upper()])
r.append([c.lower()])
else:
#this is the key step, before I know the python copy well, I wasted a lot of time here when I was attending the weekly contest of the LeetCode
tmp_list=copy.deepcopy(r)
for i in xrange(len(r)):
r[i].append(c.upper())
tmp_list[i].append(c.lower())
r=r+tmp_list
else:
if not r:
r.append([c])
else:
for i in xrange(len(r)):
r[i].append(c)
fr = []
for l in r:
fr.append(''.join(l))
return frzip: to combine and visit multiple lists
Duplicates:
Find duplicates: Floyd’s Tortoise and Hare algorithm, either linked list or an array : 287, for this type, typically can only find one duplicated element.
Remove duplicates: or it is the same to remove certain number 26,27 (in-place)
Sort array
#use two pointers
slow, faster = 0,0
for faster in xrange(1, len(nums)):
if nums[slow]!=nums[faster]:
nums[slow+1]=nums[faster]
slow+=1
return slow+1Find a certain sum in the list: or a set (Use the elements repeatly), use Dynamic Programming:
Methods:
- Sort the list or not at the begin. (O(nlogn)
- Brute force searching (recursively O(2^n))
- Hash-map (dictionary in Python), can lower the complexity by one power of n
- Recursive with memorization (DP, top-down )
- Bottom-up with memorization (DP, bottom-up)
