Example problems related to Array.
1. Implement Binary Search on a Sorted Array
Given a sorted array of integers, return the index of the given key. Return -1 if the key is not found.
# 1. Iterative Binary Search.
# Time complexity O(log n), space complexity O(1)
def binarySearch1(arr, key):
l = 0
r = len(arr)-1
if arr[l] > arr[r]: return -1
while arr[l] < arr[r]:
m = l + (r - l) // 2
if arr[m] == key:
return m
elif arr[m] > key:
r = m
else:
l = m + 1
return -1
def binarySearch1(arr, key):
l = 0
r = len(arr)-1
if arr[l] > arr[r]: return -1
while arr[l] <= arr[r]:
m = l + (r - l) // 2
if arr[m] == key:
return m
elif arr[m] > key:
r = m - 1
else:
l = m + 1
return -1
# 2. Recursive Binary Search.
# Time complexity O(log n), space complexity O(log n)
def binarySearch2(arr, key):
return recursion(arr, key, 0, len(arr)-1)
def recursion(arr, key, l, r):
if l > r: return -1
m = l + (r - l) // 2
if arr[m] == key: return m
elif arr[m] > key:
return recursion(arr, key, l, m-1)
else:
return recursion(arr, key, m+1, r)
2. Find Maximum in Sliding Window
Given a large array of integers and a window of size w, find the current maximum value in the window as the window slides through the entire array.
# Maintain a decreasing Queue
# Time complexity O(n), n is the length of the array. Space complexity O(w), w is the window size.
import collections
def find_max_sliding_window(arr, window_size):
result = []
deque = collections.deque()
n = len(arr)
if window_size == 0:
return result
for i, j in zip(range(1-window_size, 1+n-window_size), range(n)):
if i > 0 and deque[0] == arr[i-1]:
deque.popleft() # if max is removed out of the window, delete it from the deque
while deque and deque[-1] < arr[j]:
deque.pop() # keep deque decreasing
deque.append(arr[j])
if i >= 0:
result.append(deque[0]) # for each window, find the max
return result
3. Search a Rotated Array
Search for a given number in a sorted array, with unique elements, that has been rotated by some arbitrary number. Return -1 if the number does not exist.
# 1. Iterative Binary Search.
# Time complexity O(log n), space complexity O(1)
# [l, r)
def binary_search_rotated1(arr, key):
l, r = 0, len(arr)-1
if len(arr) == 0: return -1
while l < r: # [l, r)
m = l + (r - l) // 2
if arr[m] == key: return m
if arr[m] < arr[r]: # mid in right sorted half
if arr[r] < key or key < arr[m]: # key in left part
r = m
else:
l = m + 1
else: # mid in left sorted half
if arr[m] < key or key < arr[l]: # key in right part
l = m + 1
else:
r = m
return l if arr[l] == key else -1 # check if found
# [l, r]
def binary_search_rotated1(arr, key):
l, r = 0, len(arr)-1
if len(arr) == 0: return -1
while l <= r: # [l, r]
m = l + (r - l) // 2
if arr[m] == key: return m
if arr[m] < arr[r]: # mid in right sorted half
if arr[r] < key or key < arr[m]: # key in left part
r = m - 1
else:
l = m + 1
else: # mid in left sorted half
if arr[m] < key or key < arr[l]: # key in right part
l = m + 1
else:
r = m - 1
return l if arr[l] == key else -1
# 2. Recursive Binary Search.
# Time complexity O(log n), space complexity O(log n)
def binary_search(arr, l, r, key):
if l > r: return -1
if len(arr) == 0: return -1
while l <= r:
m = l + (r - l) // 2
if arr[m] == key: return m
if arr[m] < arr[r]: # mid in right sorted half
if arr[r] < key or key < arr[m]: # key in left part
return binary_search(arr, l, m-1, key)
else:
return binary_search(arr, m+1, r, key)
else: # mid in left sorted half
if arr[m] < key or key < arr[l]: # key in right part
return binary_search(arr, m+1, r, key)
else:
return binary_search(arr, l, m-1, key)
return l if arr[l] == key else -1
def binary_search_rotated2(arr, key):
return binary_search(arr, 0, len(arr)-1, key)
4. Find the Smallest Common Number
Given three integer arrays sorted in ascending order, return the smallest number that is common in all three arrays.
# Three pointers.
def find_least_common_number(a, b, c):
i = j = k = 0
while i < len(a) and j < len(b) and k < len(c):
if a[i] == b[j] and b[j] == c[k]:
return a[i]
if a[i] <= b[j] and a[i] <= c[k]: i+=1
elif b[j] <= a[i] and b[j] <= c[k]: j+=1
elif c[k] <= a[i] and c[k] <= b[j]: k+=1
return -1
5. Rotate an Array by N Elements
Given an array of integers, rotate the array by N elements where N is an integer: for positive values of N, perform a right rotation; for negative values of N, perform a left rotation.
# Slicing accounts for negative N
def rotate_array(arr, n):
length = len(arr)
n = n % length
return arr[length - n:] + arr[:length - n]
# alternative way 1
def rotate_array(arr, n):
length = len(arr)
n = n % length
if n < 0:
n += length
arr.reverse()
arr[:n] = list(reversed(arr[:n]))
arr[n:length] = list(reversed(arr[n:length]))
return arr
# alternative way 2
def rotate(arr, start, end):
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
def rotate_array(arr, n):
length = len(arr)
n = n % length
if n < 0:
n += length
rotate(arr, 0, length -1)
rotate(arr, 0, n - 1)
rotate(arr, n, length -1)
return arr
6. Find Low/High Index of a Key in a Sorted Array
Given a sorted array of integers, return the low and high index of the given key. Return -1 if the indexes are not found.
