Array Questions Part 3
56. (LC 1) Two Sum
1. Two Sum Easy
Python3
# My V (LC accepted 99, 50)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_t = {}
for i, n in enumerate(nums):
pair = target - n
if pair in hash_t:
return [hash_t[pair], i]
hash_t[n] = i
C++ [14]
nums={3,2,10,11,7,15}, target = 9
The naive approach
Iterate nums, for each number iterate the rest of nums and look for the pair_value=target-num.
E.g. 3, 9-3=6, look for 6 to the right of 3.
2, 9-2=7, look for 7 to the right of 2.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result; //for two answer indices
for (auto it1 = nums.begin(); it1 != nums.end(); ++it1){
auto it2 = find(it1+1, nums.end(), target - *it1); //it1+1 to look to the right of cur num only
if (it2 != nums.end()){ //found the number
result.push_back(it1 - nums.begin()); //iterators subtraction allows to obtain a proper number of an index, not iterator
result.push_back(it2 - nums.begin());
break; //cannot use return here, otherwise error: non-void function does not return a value in all control paths
}
}
return {}; //returning empty vector if complement was not found
}
};
Approach 2
Using hash map.
keys: nums values, values: their position
Insert all elems into the map. (The catch is not to insert all values, then traverse
again and search, but do it simultaneously.)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> _map;
for (int i = 0; i < nums.size(); ++i){
int num = nums[i];
int complement = target - num;
auto it = _map.find(complement); //returns iter if finds key in map, end of container iter otherwise. Iter points to key, value pair.
if(it != _map.end()){ //found
return {it->second, i}; //iter points at the (key,value) pair, *iter is tha pair. (*iter).mem, we want the second, i.e. value. i is the index of cur num
}
_map[num] = i; //insert into hash map, like in Python
}
return {}; //returning empty vector if complement was not found
}
};
Note how we iterate:
Approach 1 -> vector -> iterators
Approach 1 -> unordered_map -> subscripting
### My V (Approach 2 but with iterators. LC accepted 80, 30)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> _map;
vector <int> result;
for (auto it1 = nums.begin(); it1 != nums.end(); ++it1){
int complement = target - *it1;
auto it2 = _map.find(complement);
if (it2 != _map.end()){
result.push_back(it2->second);
result.push_back(it1 - nums.begin());
break;
}
_map[*it1] = it1 - nums.begin();
}
return result;
}
};
57. (LC 15) 3Sum
15. 3Sum (Medium)
Solution 0
My V (Time Limit Exceeded on case 308/313, so almost works)
(Brute force, use Python std lib.)
from itertools import combinations
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# Out of all combinations with size 3, choose those that sum to 0.
combos = [c for c in combinations(nums, 3) if sum(c) == 0]
# Choose only unique combinations
res = set([tuple(sorted(l)) for l in combos])
res = list([list(item) for item in res])
return res
Key notes:
-Pictorially:
# [-4,-1,-1,0,1,2]
# a L R
-sort input
-a is current number, use i,a enumerate(nums), calculate L,R from i.
-2 edge cases: if a is positive, if a==nums[i-1]
-nested while l<r
-if successfully found a triple, again advance Lpointer till nums[L]!=nums[L+1]
My V (LC accepted 70,18)
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums) - 1
res = []
for i, a in enumerate(nums[:n-1]):
if a > 0:
break
if i > 0 and a == nums[i-1]:
continue
L, R = i+1, n
while L < R:
if a + nums[L] + nums[R] == 0:
res.append([a,nums[L],nums[R]])
while(L < R and nums[R] == nums[R-1]): R-=1
while(L < R and nums[L] == nums[L+1]): L+=1
R-=1
L+=1
elif a+nums[L]+nums[R] > 0: R-=1
else: L+=1
return res
Solution 1 [10]
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i, a in enumerate(nums):
# Skip positive integers
if a > 0: #0
break
if i > 0 and a == nums[i - 1]: #1
continue
l, r = i + 1, len(nums) - 1 #2
while l < r:
threeSum = a + nums[l] + nums[r]
if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
res.append([a, nums[l], nums[r]])
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r: #3
l += 1
return res
#0 If current number (a) is positive, then all the following nums are positive as well (sorted array), and we won’t sum them to 0.
#1 To avoid duplicates
if it is the same number as prev, e.g. [-2,-2,0,3..], we don’t use it.
I.e. we don’t use it as the <first number> again for triplets like [-2,0,2], [-2,0,2].
(We can use it as a second like [-2,-2,4].)
#2 3 nums = Our current value and two pointers:
# [-4,-1,-1,0,1,2]
# a L R
#3 To avoid duplicates
Again if we have
# [-1,-1,-1,0,3..]
# a L
If we move L+=1, it will move to the same value, so we move L till it is a different value, or L meets R.
Solution 1, V2 [14]
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
if n < 3: return []
result = []
nums.sort()
for i in range(n-2):
if i == 0 or nums[i] != nums[i-1]:
j,k = i+1, n-1
while j < k:
sum = nums[i] + nums[j] + nums[k]
if sum == 0:
result.append([nums[i], nums[j], nums[k]])
while j < k and nums[j] == nums[j+1]: j += 1
while j < k and nums[k] == nums[k-1]: k -= 1
j, k = j+1, k-1
elif sum < 0: j += 1
else: k -= 1
return result
C++
My V (LC accepted 90, 60)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for(int i=0; i != n-2; ++i){
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i-1])
continue;
int L = i+1, R = n-1;
while(L < R){
if(nums[i] + nums[L] + nums[R] == 0){
res.push_back({nums[i], nums[L], nums[R]});
while(R > L && (nums[R] == nums[R-1])) --R;
while(R > L && (nums[L] == nums[L+1])) ++L;
--R;
++L;
}
else if(nums[i] + nums[L] + nums[R] > 0) --R;
else ++L;
}
}
return res;
}
};
Solution [14]
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
if(n < 3) return {};
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for(int i = 0; i < n-2; ++i){
if(i == 0 || nums[i] != nums[i-1]){
int j = i + 1, k = n-1;
while(j < k){
int sum = nums[i] + nums[j] + nums[k];
if(sum == 0){
result.push_back({nums[i], nums[j], nums[k]});
while(j < k && nums[j] == nums[j+1]) j++;
while(j < k && nums[k] == nums[k-1]) k--;
j++; k--;
}
else if (sum > 0) k--;
else j++;
}
}
}
return result;
}
58. (LC 16) 3Sum Closest
16. 3Sum Closest (Medium)
Keys:
-sort
-three pointers, diff var
-if threeSum > Greater than target, move RP
# <----|
# [-4,-1,1,2]
# R
-if threeSum < Less than target, move MidPoint
# |--->
# [-4,-1,1,2]
# M
Solutions:
### My V3 (LC accepted, 16, 74%)
def threeSumClosest(a, t):
a.sort()
ans = 0
dif = float("inf")
for lp in range(len(a) - 2):
rp = len(a) - 1
mp = lp + 1
while mp < rp:
summing = sum([a[lp], a[mp], a[rp]])
cur_dif = abs(summing - t)
if cur_dif < dif:
dif = cur_dif
ans = summing
if summing > t:
rp -= 1
elif summing < t:
mp += 1
else:
return t
return ans
# My V (Stdlib)
import itertools as it
def sum_closest(a, t):
combos = it.combinations(a, 3)
sums = [sum(c) for c in combos]
ans = sums[0]
dif = abs(t - ans)
for s in sums:
if abs(t - s) < dif:
ans = s
return ans
nums = [-1, 2, 1, -4]
target = 1
print(sum_closest(nums, target)) # 2
Solutions Time: O(n^2):
### 1
def threeSumClosest(nums, target):
N = len(nums)
nums.sort()
res = float('inf') # sum of 3 numbers
for t in range(N):
i, j = t + 1, N - 1
while i < j:
_sum = nums[t] + nums[i] + nums[j]
if abs(_sum - target) < abs(res - target):
res = _sum
if _sum > target:
j -= 1
elif _sum < target:
i += 1
else:
return target
return res
### 2 (pretty much the same)
def threeSumClosest(num, target):
num.sort()
mindiff = 100000
res = 0
for i in range(len(num)):
left = i + 1
right = len(num) - 1
while left < right:
sum = num[i] + num[left] + num[right]
diff = abs(sum - target)
if diff < mindiff:
mindiff = diff
res = sum
if sum == target:
return sum
elif sum < target:
left += 1
else:
right -= 1
return res
59. (LC 989) Add to Array-Form of Integer
(Easy) The array-form of an integer num is an array representing its digits in left to right order. For example, for num = 1321, the array form is [1,3,2,1]. Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.
Example 1:
Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234
Example 2:
Input: num = [2,7,4], k = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455
Example 3:
Input: num = [2,1,5], k = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021
### My v
def add_to_array(a, n):
a = [0] + a
for i in range((len(a) - 1), -1, -1):
a[i] = a[i] + (n % 10) #4+(181%10)=4+1=5
a[i - 1] += a[i] // 10 #7+5//10, i.e. +carry
a[i] = a[i] % 10 #if there was carry on a[i], chop it off
n = n // 10 #chop of right digit from 181, leaving 18
if a[0] == 0:
return a[1:]
return a
num = [2, 7, 4]
k = 181
print(add_to_array(num, k)) #[4, 5, 5]
### Solution 1
# (operation on array)
class Solution:
def addToArrayForm(self, num: List[int], k: int) -> List[int]:
s = ""
for i in num:
s += str(i)
answer = int(s) + k
return list("".join(str(answer))) #why not list(str(answer))
# Using list comprehension
class Solution:
def addToArrayForm(self, A: List[int], K: int) -> List[int]:
return [int(x) for x in str(int(''.join(str(x) for x in A))+K)]
divmod(a,b)Given two numbers (a=what you want to divide, b=divide by )
Gives as result (quotient, remainder)
>>> divmod(26, 5)
(5, 1)
### Solution 2
class Solution:
def addToArrayForm(self, num: List[int], k: int) -> List[int]:
i, carry = len(num) - 1, 0
ans = []
while i >= 0 or k or carry:
carry += (0 if i < 0 else num[i]) + (k % 10)
carry, v = divmod(carry, 10)
ans.append(v)
k //= 10
i -= 1
return ans[::-1]
Explained
E.g., Input: num = [1,2,0,0], k = 34
i, carry = len(num) - 1, 0
# We start at the LSB, i.e. last index i of array ‘num’.
Here at first iteration i=4
Set carry to 0.
while i >= 0 or k or carry:
# Because we need to carry on if k > number in array.
1)No worries, we won’t do i=-1 lookups in array nums. carry=0 if i < 0.
2)Strangely we set carry to be the result of normal sum of num[i] + k%10.
FYI k%10 is the LSB of k, here 34%10=4
First loop, i=3, carry = num[3] + 4 = 4
We set this right in the next step.
3)
carry, v = divmod(carry, 10)
>>> divmod(4, 10)
(0, 4)
Now carry is 0, v=4
FYI, if instead of 4, we had 18, then we get our carry=1 with:
>>> divmod(18, 10)
(1, 8)
4)
ans.append(v)
5)
k //= 10
i -= 1
Remove k’s LSB (34//10 = 3)
Move to the next index.
Next we will be adding 3 to num[3-1].
### Solution 3
class Solution:
def addToArrayForm(self, num: List[int], k: int) -> List[int]:
for i in reversed(range(len(num))):
k, num[i] = divmod(num[i] + k, 10)
while k > 0:
num = [k % 10] + num
k //= 10
return num
60. (LC 419) Battleships in a Board
419. Battleships in a Board Medium
Solution 1
Keys:
-Just check for each cell that has ‘X’ if the cell <immediately above> or the cell <immediately to the left> also has ‘X’. Means you already counted that ‘X’, so you can continue.
class Solution(object):
def countBattleships(self, board):
"""
:type board: List[List[str]]
:rtype: int
"""
h = len(board)
w = len(board[0]) if h else 0
ans = 0
for x in range(h):
for y in range(w):
if board[x][y] == 'X':
if x > 0 and board[x - 1][y] == 'X': #if there is a ship above
continue
if y > 0 and board[x][y - 1] == 'X': #if there is a sip to the left
continue
ans += 1
return ans
Note,
h (height) is x (first index in matrix)
Solution 2
If you overdid problems on graphs.
### My V (LC accepted 5, 8% slow)
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
rows = len(board)
cols = len(board[0])
visited = set()
ships = 0
def dfs(r,c):
if r not in range(rows) or c not in range(cols) or (
board[r][c] == '.' or (r,c) in visited):
return
visited.add((r,c))
dfs(r, c+1)
dfs(r, c-1)
dfs(r+1, c)
dfs(r-1, c)
for r in range(rows):
for c in range(cols):
if board[r][c] == 'X' and (r,c) not in visited:
dfs(r,c)
ships +=1
return ships
61. (LC 121) Best Time to Buy and Sell Stock
121. Best Time to Buy and Sell Stock (Easy)
In short: buy and sell once, return max profit.
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.
Example 2: Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
### My V
def buy_sell(a):
max_pofit, min_price = 0, a[0]
for p in a:
min_price = min(min_price, p)
max_pofit = max(max_pofit, p - min_price)
return max_pofit
### Solution 1
class Solution(object):
def maxProfit(self, prices):
if len(prices) == 0:
return 0
### NOTE : we define 1st minPrice as prices[0]
minPrice = prices[0]
maxProfit = 0
### NOTE : we only loop prices ONCE
for p in prices:
# only if p < minPrice, we get minPrice
if p < minPrice:
minPrice = p
### NOTE : only if p - minPrice > maxProfit, we get maxProfit
elif p - minPrice > maxProfit:
maxProfit = p - minPrice
return maxProfit
### Other Solutions
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans, mi = 0, inf
for v in prices:
ans = max(ans, v - mi)
mi = min(mi, v)
return ans
class Solution(object):
# @param prices, a list of integers
# @return an integer
def maxProfit(self, prices):
max_profit, min_price = 0, float("inf")
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
62. (LC 309) Best Time to Buy and Sell Stock with Cooldown
309. Best Time to Buy and Sell Stock with Cooldown (Medium)
# 1
class Solution:
def maxProfit(self, prices: List[int]) -> int:
sell = 0
hold = -math.inf
prev = 0
for price in prices:
cache = sell
sell = max(sell, hold + price)
hold = max(hold, prev - price)
prev = cache
return sell
# 2
class Solution:
def maxProfit(self, prices: List[int]) -> int:
f, f0, f1 = 0, 0, -prices[0]
for x in prices[1:]:
f, f0, f1 = f0, max(f0, f1 + x), max(f1, f - x)
return f0
# 3 Dynamic programming, O(n) [10]:
from typing import List
def maxProfit(prices: List[int]) -> int:
# State: Buying or Selling?
# If Buy -> i + 1
# If Sell -> i + 2 # +2 because +cooldown day
dp = {} # key=(i, buying) val=max_profit, dp implements cashing
def dfs(i, buying):
if i >= len(prices):
return 0
if (i, buying) in dp:
return dp[(i, buying)]
cooldown = dfs(i + 1, buying)
if buying:
buy = dfs(i + 1, not buying) - prices[i]
dp[(i, buying)] = max(buy, cooldown)
else:
sell = dfs(i + 2, not buying) + prices[i]
dp[(i, buying)] = max(sell, cooldown)
return dp[(i, buying)]
return dfs(0, True)
prices = [1, 2, 3, 0, 2]
print(maxProfit(prices))
63. (LC 122) Best Time to Buy and Sell Stock II
122. Best Time to Buy and Sell Stock II (Medium)
Key is that you can buy and sell on the same day.
-Basically you can sell each time you meet a higher price.
-If successful sell, then set <cur buy price> = <cur price> (so sell and buy on the same day).
-Add up the results.
E.g. prices=[1,2,3,4,5]
You don’t have to look for the best option, which is here buy at 1, sell at 5.
You can buy at 1, sell at 2. Then buy at 2, sell at 3 etc.
Solution 1 [2]
### Solution 1
from typing import List
import itertools
def maxProfit(prices: List[int]) -> int:
return sum(max(0, b - a) for a, b in itertools.pairwise(prices))
prices = [7,1,5,3,6,4]
print(maxProfit(prices)) # 7
# tools
itertools.pairwise(iterable)Roughly equivalent to:
pairwise(‘ABCDEFG’) –> AB BC CD DE EF FG
Solution 2 [10]
### Solution 2
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
max_profit += prices[i] - prices[i-1]
return max_profit
My V (LC accepted 50, 70%)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
cur_min = prices[0]
total_profit = 0
for price in prices:
cur_min = min(cur_min, price)
profit = price - cur_min
if profit > 0:
cur_min = price
total_profit += profit
return total_profit
Emulating as close as possible the classic buy-sell stock.
64. (LC 1014) Best Sightseeing Pair
1014. Best Sightseeing Pair (Medium)
# In short
Given an array, return the highest
values[i] + values[j] + i - j
# Keys
i - j is the distance between the sightseeing spots.
### Solution 1
class Solution:
def maxScoreSightseeingPair(self, A: List[int]) -> int:
n = len(A)
pre = A[0] + 0
res = 0
for i in range(1, n):
res = max(res, pre + A[i] - i)
pre = max(pre, A[i] + i)
return res
# The same (breaking down the steps)
from typing import List
def f(A: List[int]) -> int:
n = len(A)
pre = A[0] + 0
res = 0
for i in range(1, n):
cur_res = pre + A[i] - i
res = max(res, cur_res)
possible_pre = A[i] + i
pre = max(pre, possible_pre)
return res
# Explained solution 1
res = max(res, pre + A[i] - i)Final response, check if we found a greater
(previous spot + current spot - distance between them)
# - i, + i confusion
it might seem unfair that in
res = max(res, pre + A[i] - i)We each time subtract the full index, not the net distance (i - j).
But actually it is because in the second line:
pre = max(pre, A[i] + i)A[i] + i
+ i means the value at i will carry with it its distance.
So if our new previous = value + 3 (it is at index 3).
Then the next time we calculate response, e.g. at i=4,
max(res, value+3 - 4)
We see that if they are only 1 place apart, we end up subtracting only that 1, not 4.
==>previous CARRIES its distance with its value.
E.g. A = [2,4,10]
pre=A[0]=2, res=0
i=1
res=max(0, 2+4-1), res=5
pre=max(2, 4+1), pre=5
i=2
res=max(5, 5+10-2), res=13 (so really 5+10-2=4+10-1)
pre=max(5, 10+2), pre=12 ==>10 carries the weight of where it is at, i.e. index 2
65. (LC 605) Can Place Flowers
(Easy)
You have a long flowerbed in which some of the plots are planted, and some are not.
However, flowers cannot be planted in adjacent plots.
Given an integer array flowerbed containing 0’s and 1’s, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.
Example 1:
Input: flowerbed = [1,0,0,0,1], n = 1
Output: true
Example 2:
Input: flowerbed = [1,0,0,0,1], n = 2
Output: false
### My V
def can_plant(a, n):
a = [0] + a + [0]
cnt = 0
for i in range(1, len(a) - 1):
if not a[i] & 1:
if a[i - 1] == 0 and a[i + 1] == 0:
cnt += 1
a[i] = 1
return cnt >= n
flowerbed = [1, 0, 0, 0, 1]
print(can_plant(flowerbed, 1)) # True
print(can_plant(flowerbed, 2)) # False
### Solution 1
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
flowerbed = [0] + flowerbed + [0]
for i in range(1, len(flowerbed) - 1):
if sum(flowerbed[i - 1 : i + 2]) == 0:
flowerbed[i] = 1
n -= 1
return n <= 0
### Explained
(See explanation for solution 2 in addition.)
#Here we check if values at [i=1, i=2, i=3] all add up to 0, none is set to 1 in one go.
#We also account for the fact that we may have A = [0,0,1,0,1],
so we may plant at i=0.
Because we do:
flowerbed = [0] + flowerbed + [0]
We start the loop for i in range(1..), but we actually start at original i=0,
which is now i=1, because we prepended withappended to array 0s.
### Solution 2
class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
for i, num in enumerate(flowerbed):
if num == 1: continue
if i > 0 and flowerbed[i - 1] == 1: continue
if i < len(flowerbed) - 1 and flowerbed[i + 1] == 1: continue
flowerbed[i] = 1
n -= 1
return n <= 0
### Explained
1) If num at i is 1, continue
2) Check adjacent values to the left and right of the current i, see if they are 1,
then we cannot plant.
if i > 0 and flowerbed[i - 1] == 1: continue
# If it is not the first element (at i=0), check that element to the left (i-1)
is not 1. Else continue the loop.
if i < len(flowerbed) - 1 and flowerbed[i + 1] == 1: continue
# If we are looking not at the last element of the array (len(A)-1),
(then it has no elements to the right)
then check if element to the right (at i+1) is 1.
### Solution 3
class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
flowerbed = [0] + flowerbed + [0]
N = len(flowerbed)
res = 0
for i in range(1, N - 1):
if flowerbed[i - 1] == flowerbed[i] == flowerbed[i + 1] == 0:
res += 1
flowerbed[i] = 1
return res >= n