Array Questions Part 2
46. (LC 280) Computing an alternation
LC 280. Wiggle Sort
### Solution to Leetcode
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
for i in range(1, len(nums)):
if (i % 2 == 1 and nums[i] < nums[i - 1]) or (
i % 2 == 0 and nums[i] > nums[i - 1]
):
nums[i], nums[i - 1] = nums[i - 1], nums[i]
Task [2]. Write a program that takes an array A of n numbers, and rearranges A’s elements to get a new array B having the property that B[0] <= B[1] >= B[2] <= B[3] >= B[4] < B[5] >=….
3) But it is not necessary to sort A to achieve the desired configuration - you could simply rearrange the elements around the median, and then perform the interleaving. Median finding can be performed in time O(n), which is the overall time complexity of this approach.
Logic, O (N). You may notice that the desired ordering is very local, and it is not necessary to find the median. Iterating through the array and swapping A[i] and A[i + 1] when i is even and A[i] > A[i+1] or i is odd and A[i] < A[i + 1] achieves the desired configuration.
### Solution
def rearrange(A):
for i in range (len(A)):
A[i:i+2] = sorted(A[i:i + 2], reverse=i% 2)
### Solution my V (less magic)
def alternation(a):
a.sort()
for i in range(len(a) - 1):
if not (i & 1):
a[i], a[i + 1] = a[i + 1], a[i]
return a
A = [2, 1, 5, 7, 8] # [2, 1, 7, 5, 8]
print(alternation(A))
A = [2,1,5,7,8]
rearrange(A)
print(A) # [1, 5, 2, 8, 7]
(when i is even, the remainder = 0, setting reverse to False. When i is odd, any value of the remainder will set reverse to True)
47. (LC 204) Enumerate all primes to n
A natural number is called a prime if it is bigger than 1 and has no divisors other than 1 and itself. Write a program that takes an integer argument and returns all the primes between 1 and that integer. For example, if the input is 18, you should return <2,3,5,7,11,13,17>.
For the rule is - since if i has a divisor other than 1 and itself, it must also have a divisor that is no greater than its square root.
def is_prime(num):
for i in range(2, int(math.sqrt(num)) + 1): #Don't forget +1
if num % i == 0:
return False
return True
def primes(n):
return [x for x in range(2, n) if is_prime(x)]
print(primes(10)) #[2, 3, 5, 7]
When a number is identified as prime, we sieve it, i.e. remove all its multiples from future consideration. We use a Boolean array to encode the candidates. E.g. [F,F,T,T,T,T]. We can set the first two to false because 0 and 1 are not primes.
### Solution (sieving)
# Given n, return all primes up to and including n.
def generate_primes(n):
primes = []
# is_prime[p] represents if p is prime or not. Initially, set each to
# true, expecting 0 and 1. Then use sieving to eliminate nonprimes.
is_prime = [False, False] + [True] * (n - 1)
for p in range(2, n + 1):
if is_prime[p]: #enter only if value at index p is True
primes.append(p) #append num 2
# Sieve p's multiples.
for i in range(p, n + 1, p): #use step, range 3rd param
is_prime[i] = False
return primes
# no comments
def generate_primes(n):
primes = []
is_prime = [False, False] + [True] * (n - 1)
for p in range(2, n + 1):
if is_prime[p]:
primes.append(p)
for i in range(p, n + 1, p):
is_prime[i] = False
return primes
print(generate_primes(11)) #[2, 3, 5, 7, 11]
48. Permute the elements of an array
A permutation is a rearrangement of members of a sequence into a new sequence. A permutation can be specified by an array P, where P[i] represents the location of the element.
Do not mark elems of a, mark elems of p:
### My V3 def f(a, p): for i in range(len(a)): if p[i] < 0: continue else: ind = p[i] a[i], a[ind] = a[ind], a[i] p[ind] -= len(p)
### My V2
def perm(a, p):
for i in range(len(a)):
if type(a[i]) != tuple:
a[i] = tuple(
a[i],
)
a[i], a[p[i]] = a[p[i]], a[i]
return [t[0] for t in a]
A = ["a", "b", "c", "d"]
p = [2, 0, 1, 3]
print(perm(A, p)) #['b', 'c', 'a', 'd']
### My version, using dict to mark permuted elements
def permute(a, p):
index = 0
d = {}
while index < len(p):
for i in range(len(a)):
if a[i] not in d:
d[a[i]] = 1
a[i], a[p[index]] = a[p[index]], a[i]
index += 1
return a
A = ["a", "b", "c", "d"]
perm = [2, 0, 1, 3]
print(permute(A, perm)) #['b', 'c', 'a', 'd']
Independent cyclic permutations: We keep going forward from i to P[i] till we get back to i. After we are done with that cycle, we need to find another cycle that has not yet been applied. It can be done by storing a Boolean for each array element. But another way (that will give us O(n1) space) is to use the sign bit in the entries in the permutation-array. Specifically, we subtract n from P[i] after applying it. This means that if an entry in P[i] is negative, we have performed the corresponding move.
def apply_permutation(perm, A):
for i in range(len(A)):
next = i
# Check if perm[i] is nonnegative (i.e. check if the element at index i
# has not been moved
while perm[next] >= 0:
A[i], A[perm[next]] = A[perm[next]], A[i]
temp = perm[next]
# Subtracts len(perm) from an entry in perm to make it negative,
# which indicates the corresponding move has been performed.
perm[next] -= len(perm)
next = temp
# Restore perm.
perm[:] = [a + len(perm) for a in perm]
A = ['a','b','c','d']
perm = [2,0,1,3]
apply_permutation(perm, A)
print(A) #['b', 'c', 'a', 'd']
(Though we already got our aimed at permuted array, we will go on for some time with the loop. Then return to the main i loop, but that will finish quickly as our values in perm get negative, and while loop works only for positives.)
49. (LC 31) Compute the next permutation
Next Permutation (Medium)
# Illustration
# 1 2 3
# 2 3 1 3 1 2
# 3 2 3 1 2 1
from typing import List
def nextPermutation(nums: List[int]) -> None:
n = len(nums)
# Could add an edge case
if n <= 2:
return nums[::-1]
i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)
# if ~i:
if i != -1:
j = next((j for j in range(n - 1, i, -1) if nums[j] > nums[i]))
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1 :] = nums[i + 1 :][::-1]
1 Look for ASCENDING pattern. Find the position of an element before the pattern changes from ascending to descending, but in reverse, starting your search from index -2. In nums the pattern changes at i=2, value=3.
2 E.g. if nums=[3,2,1] then i=-1, then nums are in perfect descending order, we go to step 3 right away. if i!=-1, that is if the pattern starts somewhere ‘in the middle’ of the list, we do one more step. Look for a number greater than num at i, to the right of i, find the first such num. In [0,1,3,10,9,4,2,0], i=3, the first greater num at j is 4. To find j=4, we iterate (from end, till i, in reverse) -> (range(len-1, i=2, -1)) Swap values at i and j -> swap 3 and 4. [0,1,4,10,9,3,2,0]
3 Reverse numbers between i and end of array (not including i itself): [0,1,4,0,2,3,9,10]
i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)in range(n - 2, -1, -1) -> from len-2, till 0-1 to include 0, step backwards -1next((iterator), -1) -> -1 is the default.if ~i: OR if i!=-1:>>> i=-1
>>> ~i
0
>>> ~i == True
False
>>> ~i == False
True
import itertools as it
def next_perm(a):
p = it.permutations(a, len(a))
next(p) # just gives current array
return list(next(p)) # next call gives next permutation
nums = [1, 2, 3] # expect [1,3,2]
print(next_perm(nums)) #[1, 3, 2]
nums = [3, 2, 1] # expect [1,2,3]
print(next_perm(nums)) # [3, 1, 2] #**
>>> n2=permutations([1,2,3],3)
>>> list(n2)
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
>>> p=permutations([3,2,1],3)
>>> list(p)
[(3, 2, 1), (3, 1, 2), (2, 3, 1), (2, 1, 3), (1, 3, 2), (1, 2, 3)]
50. Sample offline data
Implement an algorithm that takes as input an array of elements and returns a subset of the given size of the array elements. All subsets should be equally likely. Return the result in input array itself.
# Practical applications - To select a random subset of customers to test a new UI (see if it increases the visit duration) before rolling out the change.
### Solution
import random
def random_sampling(k, A): #k is size of the new array
for i in range(k):
# Generate a random index in [i, len(A) - 1].
r = random.randint(i, len(A) - 1)
A[i], A[r] = A[r], A[i]
return A[:k]
# OR
# index = random.randrange(i, len(a))
A = [3,7,5,11]
print(random_sampling(3, A)) #example output [7, 11, 5]
# My note -
Since we use the stdlib module random anyway,
why not use the dedicated .sample(list, sample_size)
print(random.sample(A, 3)) #[5, 3, 11]
51. Sample online data
(In practice it can be to provide a uniform sample of packets for a network session.)
Task [2] - Given input A size n, write a program that reads input A maintaining a uniform random subset of size k.
### V0 my
import random
def random_subset1(a, k):
random.shuffle(a)
return a[:k]
### V2 my
import random
def random_subset2(a, k):
for i in range(k):
ri = random.randrange(i, len(a)) #generate random index
a[i], a[ri] = a[ri], a[i]
return a[:k]
### V1 My version (don't know if we can use it here)
import random
def random_subset(a, k):
for i in range(k):
swap_i = random.choice(range(i, len(a)))
a[i], a[swap_i] = a[swap_i], a[i]
return a[:k]
a = [1, 2, 4, 5, 3]
print(random_subset(a, 3)) #2 runs, OUT:[1, 3, 2], [4, 2, 5]
itertools.islice(iterable, stop)
>>> a = itertools.islice('ABCD', 2)
>>> a
<itertools.islice object at 0x7fa8b0b5c540>
>>> list(a)
['A', 'B']
Solution
import itertools, random
def online_random_sample(it, k):
sampling_results = list(itertools.islice(it, k))
num_seen_so_far = k
for x in it:
num_seen_so_far += 1
idx_to_replace = random.randrange(num_seen_so_far)
if idx_to_replace < k:
sampling_results[idx_to_replace] = x
return sampling_results
it = list('pqrtuv')
print(online_random_sample(it, 2))
# 3 calls produce random results: ['v', 'q'], ['v', 'p'], ['p', 'q']
# With comments
def online_random_sample(it, k):
# Gets us first result [p, q] (slice input data[0:2])
sampling_results = list(itertools.islice(it, k))
# Start sampling starting at index 2, before that is our initial sample
num_seen_so_far = k
for x in it:
num_seen_so_far += 1 #2+1=3
# In the first loop, choose random index out of 0,1,2.
# As range() randrange() stops before the given number.
idx_to_replace = random.randrange(num_seen_so_far)
if idx_to_replace < k: #**
sampling_results[idx_to_replace] = x
return sampling_results
52. (LC 384) Compute a random permutation
384. Shuffle an Array - Medium
Design an algorithm that creates uniformly random permutations of {0, 1,…,n - 1}.
Notes: Generating random permutations with equal probability is not as straightforward as it seems. Iterating and swapping each element with another randomly does not generate all permutations with equal probability. E.g. when there are n=3 elements. The number of permutations is 3! = 6. Ways to choose elements to swap is 3**3 = 27. Since 27 is not divisible by 6, some permutations correspond to more ways than others.
1)First random number is chosen between index 0 and index 3. We get e.g. index to update with=1, we swap current index 0 with index 1. Get A=[1,0,2,3].
2)Next choose from indices 1-3, e.g. random choice gives us index 3, swap i=1 with index=3. A=[1,3,0,2] etc.
We iterate through A and swap current index with a randomly generated index from only the remaining indices. This reminds of the function we used earlier. We are going to use it as a helper function for the current solution.
### Solution
import random
def random_sampling(k, A): #k is size of the new array
for i in range(k):
r = random.randint(i, len(A) - 1) #r is random index
A[i], A[r] = A[r], A[i]
return A[:k]
def compute_random_permutation(n):
permutation = list(range(n))
random_sampling(n, permutation)
return permutation
print(compute_random_permutation(5))
# OUT
# [2, 3, 0, 4, 1]
# [0, 3, 2, 4, 1]
### V1 my
# The main point - choose a random index from len of array.
# Swap current index with random index.
# Diminish indices to randomly choose from by 1 (or len - current index)
import random
def random_permut(n):
a = list(range(n + 1))
le = len(a) - 1
for i in range(le):
index = random.randint(i, le)
a[i], a[index] = a[index], a[i]
return a
print(random_permut(5)) # [1, 0, 2, 3, 5, 4], run2 [2, 5, 3, 1, 4, 0]
### V2 my
import random
def shuffle_array2(a):
for i in range(len(a) - 1):
ri = random.randrange(i, len(a))
a[i], a[ri] = a[ri], a[i]
return a
### FYI. Python stdlib tools
#1
import random
def shuffle_array(a):
random.shuffle(a)
return a
#2
>>> import itertools
>>> it = itertools.permutations(range(0,4))
>>> it.__next__()
(0, 1, 2, 3)
>>> it.__next__()
(0, 1, 3, 2)
53. Generate nonuniform random numbers
# Practical application - Load test for a server. You have the inter-arrival time of requests to the server over a period of one year. You have a histogram of the distribution of the arrival times of requests. In the load test you would like to simulate data arriving at the same time as the distribution observed historically.
# Solution logic
1) with itertools.accumulate(probabilities) we make a list that accumulates probabilities -> P0, P0+P1, P0+P1+P2 etc. The interval between two such accumulated values will correspond to the probability of each element (intervals like this (0.0, 0.5), (0.5, 0.833) etc., our accumulated list [0.0, 0.5, 0.833 ..]
2) We use random.random() to generate a value between 0 and 1. E.g. 0.6 is generated.
3) We use bisect.bisect() to find the index where that value would be in our accumulated list. 0.6 in [0.0, 0.5, 0.833 ..] would be at index 2, after 0.5, so we would return values[2] which is ([3,5,7,11]) 7.
The take away - we choose randomly from <probabilities of the numbers>.
That way we generate one of the n numbers according to the specified probabilities. (Meaning if the probability of a number ([3,5,7,11]) is high, then the chances that the randomly generated value (between 0,1) will fall in that range are higher.)
print(bisect.bisect([0.0, 0.5, 0.83, 0.9, 1.0 ], 0.4)) #1
print(bisect.bisect([0.0, 0.5, 0.83, 0.9, 1.0 ], 0.5)) #2
### Solution
import itertools, bisect, random
def nonuniform_random_number_generation(values, probabilities):
prefix_sum_of_probabilities = list(itertools.accumulate(probabilities))
interval_idx = bisect.bisect(prefix_sum_of_probabilities, random.random())
return values[interval_idx]
# my rewrite
def non_uniform_random_num(a, p):
probabilities = list(itertools.accumulate(p))
r = random.random()
index = bisect.bisect_left(probabilities, r)
return a[index]
a = [2, 4, 6, 7]
p = [0.3, 0.2, 0.4, 0.1]
print(non_uniform_random_num(a, p))
# Let's see what's going on. Adding print calls.
def nonuniform_random_number_generation(values, probabilities):
prefix_sum_of_probabilities = list(itertools.accumulate(probabilities))
print(prefix_sum_of_probabilities)
interval_idx = bisect.bisect(prefix_sum_of_probabilities, random.random())
print(interval_idx)
return values[interval_idx]
values = [3,5,7,11]
probabilities = [9/18, 6/18, 2/18, 1/18]
print(nonuniform_random_number_generation(values, probabilities))
# OUT
# [0.5, 0.8333333333333333, 0.9444444444444444, 1.0] #yeah, starts from non-zero
# 1 #index
# 5
Time O(n) which is time to create the array of intervals. Space O(n).
54. (LC 36) Valid Sudoku
36. Valid Sudoku (Medium)
Version 1. If you are given a solved, completely filled, Sudoku.
# Logic. We check that no row, column, or 3x3 2D subarray contains duplicates.
### Solution
import itertools
def sudoku_ok(line):
return (len(line) == 9 and sum(line) == sum(set(line)))
def check_sudoku(grid):
bad_rows = [row for row in grid if not sudoku_ok(row)]
grid = list(zip(*grid))
bad_cols = [col for col in grid if not sudoku_ok(col)]
squares = []
for i in range(0, 9, 3):
for j in range(0, 9, 3):
square = list(itertools.chain(row[j:j+3] for row in grid[i:i+3]))
square = [n for i in square for n in i]
squares.append(square)
bad_squares = [square for square in squares if not sudoku_ok(square)]
return not (bad_rows or bad_cols or bad_squares)
sudoku = [[5,3,4,6,7,8,9,1,2],
[6,7,2,1,9,5,3,4,8],
[1,9,8,3,4,2,5,6,7],
[8,5,9,7,6,1,4,2,3],
[4,2,6,8,5,3,7,9,1],
[7,1,3,9,2,4,8,5,6],
[9,6,1,5,3,7,2,8,4],
[2,8,7,4,1,9,6,3,5],
[3,4,5,2,8,6,1,7,8] # <-- not valid sudoku, two 8s
]
board = [[7, 9, 2, 1, 5, 4, 3, 8, 6],
[6, 4, 3, 8, 2, 7, 1, 5, 9],
[8, 5, 1, 3, 9, 6, 7, 2, 4],
[2, 6, 5, 9, 7, 3, 8, 4, 1],
[4, 8, 9, 5, 6, 1, 2, 7, 3],
[3, 1, 7, 4, 8, 2, 9, 6, 5],
[1, 3, 6, 7, 4, 8, 5, 9, 2],
[9, 7, 4, 2, 1, 5, 6, 3, 8],
[5, 2, 8, 6, 3, 9, 4, 1, 7]]
print(check_sudoku(sudoku)) #False
print(check_sudoku(board)) #True
grid = list(zip(*grid))>>> Z = list(zip((1, 2, 3), (10, 20, 30), (5,7,6)))
>>> Z
[(1, 10, 5), (2, 20, 7), (3, 30, 6)]
for i in range(0, 9, 3):
for j in range(0, 9, 3):
Version 2. Check for validity a partially filled board (0 value for blank entries). [10]
# Explained. First of all - do not over complicate.
All that the task asks is to check that each row, column and 3x3 cube is valid, i.e. all values in each of these are numbers 1-9 without duplicates. So for a row=[1,2,3,4,5,6,’.’,’.’,9] - all we need to check is if all the VISIBLE filled in values satisfy the rules. NOT if the blank spaces can “potentially” cause duplicates (when rows, columns, cubes meet). So you evaluate the board as of its state “right now”.
How we will identify the 3x3 cubes
Big O
O(9**2) both time and space, because we iterate through each col, row and also store the values in hash sets.
### Solution
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
cols = collections.defaultdict(set)
rows = collections.defaultdict(set)
squares = collections.defaultdict(set) # key is a tuple= (r /3, c /3)
for r in range(9):
for c in range(9):
if board[r][c] == ".":
continue
if (
board[r][c] in rows[r]
or board[r][c] in cols[c]
or board[r][c] in squares[(r // 3, c // 3)]
):
return False
cols[c].add(board[r][c])
rows[r].add(board[r][c])
squares[(r // 3, c // 3)].add(board[r][c])
return True
collections.defaultdict(set)
We will use hash sets.
So the lines like this of our code:
cols[c].add(board[r][c]) Will do stuff like this:
>>> D = collections.defaultdict(set)
>>> D[5].add(30)
>>> D
defaultdict(<class 'set'>, {5: {30}})
>>> D[5].add(31)
>>> D
defaultdict(<class 'set'>, {5: {30, 31}}) #Yes, sets have {}
squares[(r // 3, c // 3)].add(board[r][c])
What this means is that the key for the ‘squares’ hash set is a tuple. So it does this:
>>> D[(1,1)].add(8)
>>> D
defaultdict(<class 'set'>, {5: {30, 31}, (1, 1): {8}}) <=== adds (1, 1): {8}
55. (LC 118) Compute rows in Pascal’s triangle
118. Pascal’s Triangle (Easy)
Example of the first 5 rows in Pascal’s triangle:
# Visualization
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]
Each row has one more entry than the previous one. Each entry is the sum of adjacent numbers above.
Write a program which takes as input a nonnegative integer n and returns the first n rows of Pascal’s triangle. Hint: Write the given fact as an equation.
### Solution
Space and time O(n**2)
def generate_pascal_triangle(n):
result = [[1] * (i+1) for i in range(n)]
for i in range(n):
for j in range(1, i):
result[i][j] = result[i-1][j-1] + result[i-1][j]
return result
print(generate_pascal_triangle(5))
### Less magic version, V1
def pascal_triangle(n):
pt = []
for k in range(1, n + 1):
pt.append([1] * k)
for i in range(2, n):
for j in range(1, i): # i because 3 items in 3rd row, 4 items in 4th row etc
pt[i][j] = pt[i - 1][j - 1] + pt[i - 1][j]
# Don't be tempted to do [j+1] !!
# item above j to the right is not j+1, it is j, because 1 less item above
return pt[n - 1] #here just returning the row n
### V2
def pasca(n):
tri = []
for i in range(n):
row = [1] * (i + 1)
for j in range(1, i):
row[j] = tri[i - 1][j - 1] + tri[i - 1][j]
tri.append(row)
return tri
### Explained (the magic version)
result = [[1] * (i+1) for i in range(n)]
Initializes triangle:
[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1, 1]]
for i in range(n):
for j in range(1, i):
result[i][j] = result[i-1][j-1] + result[i-1][j]### My V3
def pasca(n):
ans = [[1], [1, 1]]
for i in range(2, n):
ans.append([0] * (i + 1))
for j in range(0, i + 1):
if j == 0 or j == i:
ans[i][j] = 1
else:
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]
return ans
print(pasca(5)) #[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]