Array Question Summary
Python Array Trick
High level thoughts:
- it is simple to iterative array with python iterator, but some array method requires index, in this case we should use index to iterate
- be careful about the index operation (see below)
- sometimes it is good to iterate backward
- this is particular true when you want to delete some element (pop(i))
- Be familiar with common used high level list function
- map
- reduce
- filter
- sorted
- reversed
Array Syntax Shortcut
S.sort()
reversed(a) # reverse a list
>>> reversed(a)
<listreverseiterator object at 0x1005dd9d0>
Array index computation
assume array index start from 0
let start = 0
end = len(array) - 1
middle = (start + end)/2
- if the array has odd length, then middle is exactly at the middle
- if even length, then middle points to the start of second half array
Nested Array operation
if we want to modify array in place, should use:
matrix[:] = zip(*matrix[::-1])
This code will rotate matrix clockwise by 90 degree
or counter-clockwise:
zip(*original)[::-1]
Questions
228. Summary Ranges
Three versions of the same algorithm, all take O(n) time.
Solution 1
Just collect the ranges, then format and return them.
def summaryRanges(self, nums):
ranges = []
for n in nums:
if not ranges or n > ranges[-1][-1] + 1:
# when ranges = [], 'if ranges' will fail
ranges += [], #ranges.append([]), see below
ranges[-1][1:] = n, #r[1:] = [n]
return ['->'.join(map(str, r)) for r in ranges]
Solution 2
A variation of solution 1, holding the current range in an extra variable r
to make things easier. Note that r contains at most two elements, so the in-check takes constant time.
def summaryRanges(self, nums):
ranges, r = [], []
for n in nums:
if n-1 not in r:
r = []
ranges += r,
r[1:] = n,
return ['->'.join(map(str, r)) for r in ranges]
About the commas :-)
Three people asked about them in the comments, so I'll also explain it here as well. I have these two basic cases:
ranges += [], r[1:] = n,
Why the trailing commas? Because it turns the right hand side into a tuple and I get the same effects as these more common alternatives:
ranges += [[]] or
ranges.append([])
r[1:] = [n]
Without the comma, ...
ranges += []
wouldn't add []
itself but only its elements, i.e., nothing.
r[1:] = n
wouldn't work, because my n
is not an iterable.
Why do it this way instead of the more common alternatives I showed above? Because it's shorter and faster (according to tests I did a while back).
189. Rotate Array
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7]
is rotated to [5,6,7,1,2,3,4]
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Hint:
Could you do it in-place with O(1) extra space?
Related problem: Reverse Words in a String II
def rotate(self, nums, k):
while k > 0:
nums.insert(0, nums.pop())
k -= 1
class Solution:
# @param nums, a list of integer
# @param k, num of steps
# @return nothing, please modify the nums list in-place.
def rotate(self, nums, k):
n = len(nums)
k = k % n # why this step ???
nums[:] = nums[n-k:] + nums[:n-k]
A little important thing to be cautious:
nums[:] = nums[n-k:] + nums[:n-k]
can't be written as:
nums = nums[n-k:] + nums[:n-k]
on the OJ.
The previous one can truly change the value of old nums, but the following one just changes its reference to a new nums not the value of old nums.
# a little simplification
def rotate(self, nums, k):
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
1. Two Sum
Consider different scenarios:
- unique solution is not guaranteed
- input could contain duplicates too
- target is double as some elements, e.g.: [3,2,4]
Ideal right solution with hash table:
# O(n) time
def twoSum(self, nums, target):
if len(nums) <= 1:
return False
buff_dict = {}
'''
how to better understanding this short algorithm:
- think this single for loop as to 'process' each number within nums:
- if
'''
for i in range(len(nums)):
# if nums[i] is the solution we look for, then just return
# this algorithm will only return the first matched tuple
if nums[i] in buff_dict:
return [buff_dict[nums[i]], i]
else:
# if nums[i] is not solution, then process it for future element of nums
# in this way, it avoid error in next solution, like error for [3,2,4]
# it also handle duplication automatically
buff_dict[target - nums[i]] = i
Classical WRONG solution:
# A WRONG solution:
def twoSum(self, nums, target):
'''
This solution is WRONG !!!
e.g. {2, 2, 11, 15}, target 4, Hashmap will be overriden for this input. How do you handle this?
- problem 1: When adding a number to the hashmap should check if the key is already in . If true you have to check whether the double of the number is equal with the target.
- problem 2: Also if you have (3,2,4) target 6. You will get 0,0 wich is not correct. (and this is even trickier to solve)
--- JUST don't use this approach !!
'''
if len(nums) <= 1:
return False
map = {}
for i in range(len(nums)):
# better: for (i, num) in emuerate(nums):
map[nums[i]] = i
for i in range(len(nums)):
if (target - nums[i]) in map.keys():
print target - nums[i]
print map[(target - nums[i])]
return [ i, map[(target - nums[i])] ]
Use sort ! O(nlog(n)) time complexity
Sort method: sorting the input gives the array a good property to keep and good indication for moving the head and tail pointers. Here is the detailed steps.
- Sort the input in increasing order
- make two pointers i, j pointing at the head and tail elements of the sorted array
- by comparing the related order between the target and the sum of the two elements pointed by the current head/tail pointers, we decide how to move the pointers to test next (copyright @sigmainfy) potential pairs
- If the target is bigger, we move the head pointer forward by one step and thus try to increase the sum, if the target is smaller we move the tail head towards the head by one step and thus try to decrease the sum a bit, if target is equal to the sum, then we are done by the assumption that there is only one such pair
- we repeat step 3 and 4 until i >= j or we find a solution
88. Merge Sorted Array
Start from back of list
def merge(self, nums1, m, nums2, n):
while m > 0 and n > 0:
if nums1[m-1] >= nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
if n > 0:
nums1[:n] = nums2[:n]
78. Subsets
# DFS recursively
def subsets1(self, nums):
res = []
self.dfs(sorted(nums), 0, [], res)
return res
def dfs(self, nums, index, path, res):
res.append(path)
for i in xrange(index, len(nums)):
self.dfs(nums, i+1, path+[nums[i]], res)
# Bit Manipulation
def subsets2(self, nums):
res = []
nums.sort()
for i in xrange(1<<len(nums)):
tmp = []
for j in xrange(len(nums)):
if i & 1 << j: # if i >> j & 1:
tmp.append(nums[j])
res.append(tmp)
return res
# Iteratively
def subsets(self, nums):
res = [[]]
for num in sorted(nums):
res += [item+[num] for item in res] #<--- Remember this way of using list comprehension!!!
return res
90. Subsets II
???
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
- We can just remove the duplicate and use previous solution
def subsetsWithDup(self, S):
res = [[]]
S.sort()
for i in range(len(S)):
if i == 0 or S[i] != S[i - 1]:
l = len(res)
for j in range(len(res) - l, len(res)):
res.append(res[j] + [S[i]])
return res
54. Spiral Matrix
def spiralOrder(self, matrix):
ret = []
while matrix:
ret += matrix.pop(0)
if matrix and matrix[0]:
for row in matrix:
ret.append(row.pop())
if matrix:
ret += matrix.pop()[::-1]
if matrix and matrix[0]:
for row in matrix[::-1]:
ret.append(row.pop(0))
return ret
59. Spiral Matrix II
Solution 3: Walk the spiral - 52 ms, 9 lines (a very smart approach!!, can also be used to print spiral matrix problem)
def generateMatrix(self, n):
A = [[0] * n for _ in range(n)]
i, j, di, dj = 0, 0, 0, 1
for k in xrange(n*n):
A[i][j] = k + 1
if A[(i+di)%n][(j+dj)%n]:
di, dj = dj, -di
i += di
j += dj
return A
Solution 1: Build it inside-out - 44 ms, 5 lines
Start with the empty matrix, add the numbers in reverse order until we added the number 1. Always rotate the matrix clockwise and add a top row:
(don't understand it)
def generateMatrix(self, n):
A, lo = [], n*n+1
while lo > 1:
lo, hi = lo - len(A), lo
A = [range(lo, hi)] + zip(*A[::-1]) # zip(* list) used to unzip a list
#zip(*matrix [::-1]) :Rotate the matrix by 90 degrees (clockwise).
return A
zip()
in conjunction with the * operator can be used to unzip a list:
**Solution 4:Recursion **
???
#zip(*matrix [::-1]) :Rotate the matrix by 90 degrees (clockwise).
def generateMatrix(self, n):
def gen(l, w, b):
#Generate a l*w Matrix. the begin number is b.
return l * [[]] and [range(b, b+l)] + map(list,zip(*gen(w-1, l, b+l)[::-1]))
return gen(n, n, 1)
75. Sort Colors
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?
# this approach is not as good as the cpp ones below
def sortColors(self, nums):
i = j = 0
for k in xrange(len(nums)):
v = nums[k]
nums[k] = 2 #this is key step! so we don't need to swap
if v < 2:
nums[j] = 1
j += 1
if v == 0:
nums[i] = 0
i += 1
The idea is to sweep all 0s to the left and all 2s to the right, then all 1s are left in the middle.
class Solution {
public:
void sortColors(int A[], int n) {
int second=n-1, zero=0;
for (int i=0; i<=second; i++) {
while (A[i]==2 && i<second) swap(A[i], A[second--]);
while (A[i]==0 && i>zero) swap(A[i], A[zero++]);
/* this second line is not really exclusive to first line, coz after first line swap, A[i] can be zero again.
This is trick to understand: need to use while to keep swap 0 and 2 forward or backward
*/
}
}
};
33. Search in Rotated Sorted Array (Hard)
def search(self, nums, target):
if not nums:
return -1
low, high = 0, len(nums) - 1 # index, not value
while low <= high:
mid = (low + high) / 2
if target == nums[mid]:
return mid
if nums[low] <= nums[mid]:
# Key idea: make comparison test with the half array that don't contain turning point
# first subarray is in order (turning point in second half):
if nums[low] <= target <= nums[mid]:
# if target is in first half:
high = mid - 1
else:
low = mid + 1
else:
# first half array has turning point
if nums[mid] <= target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return -1
4. Median of Two Sorted Arrays (Hard)
-- don't understand how to solve it !!!
11. Container With Most Water
In the first thought, we need to have nested for loop to scan over the array in order to find the minimal combination. However, by some clever thought, we can discover the minimal combination by using single one pass for loop.
Review the note and homework in CS341. I have think quite deep for this kind problems.
Proof
Here is the proof. Proved by contradiction:
Suppose the returned result is not the optimal solution. Then there must exist an optimal solution, say a container with aol and aor (left and right respectively), such that it has a greater volume than the one we got. Since our algorithm stops only if the two pointers meet. So, we must have visited one of them but not the other. WLOG, let's say we visited aol but not aor. When a pointer stops at a_ol, it won't move until
The other pointer also points to aol. In this case, iteration ends. But the other pointer must have visited aor on its way from right end to aol. Contradiction to our assumption that we didn't visit aor.
The other pointer arrives at a value, say arr, that is greater than aol before it reaches aor. In this case, we does move aol. But notice that the volume of aol and arr is already greater than aol and aor (as it is wider and heigher), which means that aol and aor is not the optimal solution -- Contradiction!
Both cases arrive at a contradiction.
https://leetcode.com/discuss/37631/simple-and-clear-proof-explanation
def maxArea(self, height):
i, j = 0, len(height) - 1
water = 0
while i < j:
water = max(water, (j - i) * min(height[i], height[j]))
'''
The smaller one of first and last line doesn't support a higher water level and can thus be safely removed from further consideration.
Note: the reasoning here is, we already keep record of current_max.
A shorter line don't have the potential of support higher future water level, therefore throw it out.
'''
if height[i] < height[j]:
i += 1
else:
j -= 1
return water
15. 3Sum
Find all unique triplets in the array which gives the sum of zero.
Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- The solution set must not contain duplicate triplets.
The idea is to sort an input array and then run through all indices of a possible first element of a triplet. For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array. Also we want to skip equal elements to avoid duplicates in the answer without making a set or smth like that. Time complexity: O(n^2)
# Time complexity: O(n^2)
def threeSum(self, nums):
""" :type nums: List[int] :rtype: List[List[int]] """
nums.sort()
res = []
for i in xrange(len(nums)):
if i != 0 and nums[i] == nums[i-1]: continue
# if i==0, then we don't have nums[i-1]
# this is to avoid d
target = -nums[i]
l, r = i+1, len(nums)-1
while l < r:
if nums[l] + nums[r] == target:
res.append((nums[i], nums[l], nums[r]))
while l < r and nums[l] == nums[l+1]: l += 1
while l < r and nums[r] == nums[r-1]: r -= 1
l += 1
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else: r -= 1
return res
48. Rotate Image
Input:[[1,2],[3,4]]
Expected:[[3,1],[4,2]]
Utilize python's syntax:
# Rotate the matrix by 90 degrees (clockwise): zip(*matrix[::-1])
# or counter-clockwise: zip(*matrix)[::-1]
def rotate(self, matrix):
matrix[:] = zip(*matrix[::-1])
Without relying on python's syntax:
/*
* clockwise rotate
* first reverse up to down, then swap the symmetry
* 1 2 3 7 8 9 7 4 1
* 4 5 6 => 4 5 6 => 8 5 2
* 7 8 9 1 2 3 9 6 3
*/
void rotate(vector<vector<int> > &matrix) {
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
/*
* anticlockwise rotate
* first reverse left to right, then swap the symmetry
* 1 2 3 3 2 1 3 6 9
* 4 5 6 => 6 5 4 => 2 5 8
* 7 8 9 9 8 7 1 4 7
*/
void anti_rotate(vector<vector<int> > &matrix) {
for (auto vi : matrix) reverse(vi.begin(), vi.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
34. Search for a Range
???
https://leetcode.com/discuss/22788/search-position-target-target-simple-python-with-little-trick
283. Move Zeroes (S)
class Solution(object):
# sol1: iterate forward, complicated
def moveZeroes(self, nums):
# it is faster if I scan from back. In that case I don't need num_operation
i = 0
num_operation = 0
while i < len(nums) and num_operation < len(nums):
num_operation += 1
print nums[i]
if nums[i]==0:
nums.pop(i)
nums.append(0)
else:
i += 1
# sol2: don't use index to iterate, wrong:
def moveZeroes(self, nums):
for i in reversed(nums):
print '--',i
if i==0:
print '==',i
nums.pop(i) # pop requires index, so we need to iterate with index
nums.append(0)
# sol3: iterate backward, simple:
def moveZeroes(self, nums):
i = len(nums) - 1
while i >= 0:
if nums[i] == 0:
nums.pop(i)
nums.append(0)
i -= 1
136. Single Number (M)
def singleNumber1(self, nums):
dic = {}
for num in nums:
dic[num] = dic.get(num, 0)+1
for key, val in dic.items():
if val == 1:
return key
def singleNumber2(self, nums):
res = 0
for num in nums:
res ^= num
return res
def singleNumber3(self, nums):
return 2*sum(set(nums))-sum(nums)
def singleNumber4(self, nums):
return reduce(lambda x, y: x ^ y, nums)
def singleNumber(self, nums):
return reduce(operator.xor, nums)
