Lists-Array Flashcards
Check if any two intervals intersects among a given set of intervals.
An interval is represented as a combination of start time and end time. Given a set of intervals, check if any two intervals intersect.
Input: arr[] = {{1, 3}, {5, 7}, {2, 4}, {6, 8}}
Output: true
The intervals {1, 3} and {2, 4} overlap
time_complexity: nlog(n) (sorting) + n= nlog(n)
def check(array):
array.sort(key = lambda x: x[0])
for i in range(1, len(array)):
if array[i][0] <= array[i-1][1]:
return (True)
return False
Check if a subarray with 0 sum exists or not.
Given an integer array, check if it contains a subarray having zero-sum.
Input: { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }
Output: Subarray with zero-sum exists
The subarrays with a sum of 0 are:
{ 3, 4, -7 }
{ 4, -7, 3 }
{ -7, 3, 1, 3 }
{ 3, 1, -4 }
{ 3, 1, 3, 1, -4, -2, -2 }
{ 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }
We can easily solve this problem in linear time by using hashing. The idea is to use a set to check if a subarray with zero-sum is present in the given array or not. Traverse the array and maintain the sum of elements seen so far. If the sum is seen before (i.e., the sum exists in the set), return true as there exists at least one subarray with zero-sum that ends at the current index; otherwise, insert the sum into the set.
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the size of the input.
def hasZeroSumSublist(nums):
check_set = set()
check_set.add(0)
sum_=0
for i in range(len(nums)):
sum_+=nums[i]
if sum_ in check_set:
print("sub array with zero exists")
check_set.add(sum_)
what is Multimap?
write a utility function to insert value to multi map
A Multimap is a map that allows the mapping of a single key to multiple values.
example: d ={A:[1,2,4], B:[3,5,6]}
def insert (d, key, value):
d.setdeafult ( key,[ ]).append(value)
Print all subarrays with 0 sum
Given an integer array, print all subarrays with zero-sum.
input: { 4, 2, -3, -1, 0, 4 }
Subarrays with zero-sum are
{ -3, -1, 0, 4 }
{ 0 }
We can use multimap to print all subarrays with a zero-sum present in the given array. The idea is to create an empty multimap to store all subarrays’ ending index having a given sum. Traverse the array and maintain the sum of elements seen so far. If the sum is seen before, at least one subarray has zero-sum, which ends at the current index. Finally, print all such subarrays.
___ Time complexity is n2. we calculate sum in linear time. otherwise in Brute Force we had n3. n2 for all sub arrays and n for sum.
******* code********************* # Utility function to insert into the dictionary
def insert(d, key, value):
# if the key is seen for the first time, initialize the list
d.setdefault(key, []).append(value)
# Function to print all sublists with a zero-sum present in a given list def printallSublists(nums):
# create an empty dictionary to store the ending index of all
# sublists having the same sum
d = {}
# insert (0, -1) pair into the dictionary to handle the case when
# sublist with zero-sum starts from index 0
insert(d, 0, -1)
total = 0
# traverse the given list
for i in range(len(nums)):
# sum of elements so far
total += nums[i]
# if the sum is seen before, there exists at least one
# sublist with zero-sum
if total in d:
list = d.get(total)
# find all sublists with the same sum
for value in list:
print('Sublist is', (value + 1, i))
# insert (sum so far, current index) pair into the dictionary
insert(d, total, I)
https://www.techiedelight.com/find-sub-array-with-0-sum/
Sort binary array in linear time
Given a binary array, sort it in linear time and constant space. The output should print all zeroes, followed by all ones.
this question is similar to move zeros to left in linear time and constant space:
def sort_binary(nums):
read_idx = len(nums)-1
write_idx = len(nums)-1
while read_idx > 0 :
if nums[read_idx]!=0:
nums[write_idx]= nums[read_idx]
write_idx-=1
read_idx -=1
while write_idx >0:
nums[write_idx]=0
write_idx-=1 return nums
or
# Function to sort a binary list in linear time def sort(A):
# count number of 0's
zeros = A.count(0)
# put 0's at the beginning
k = 0
while zeros:
A[k] = 0
zeros = zeros - 1
k = k + 1
# fill all remaining elements by 1
for k in range(k, len(A)):
A[k] = 1
if __name__ == ‘__main__’:
A = [0, 0, 1, 0, 1, 1, 0, 1, 0, 0] sort(A)
# print the rearranged list
print(A)
Find the duplicate element in a limited range array
Given a limited range array of size n containing elements between 1 and n-1 with one element repeating, find the duplicate number in it without using any extra space.
We have limited range arry!!!
Approach 1: Using Hashing \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_- The idea is to use hashing to solve this problem. We can use a visited boolean array to mark if an element is seen before or not. If the element is already encountered before, the visited array will return true. ******************************* def findDuplicate(nums):
# create a visited list of size `n+1`
# we can also use a dictionary instead of a visited list
visited = [False] * (len(nums) + 1)
# for each element in the list, mark it as visited and
# return it if seen before
for i in nums:
# if the element is seen before
if visited[i]:
return i
# mark element as visited
visited[i] = True
# no duplicate found
return -1
_____________________
Approach 4: Using Difference in Sum
def findDuplicate(nums):
actual_sum = sum(nums) expected_sum = len(nums) * (len(nums) - 1) // 2 return actual_sum - expected_sum
what is the difference between subarray and subsequense?
Unlike subsequences, subarrays are required to occupy consecutive positions within the original array.
Find the largest subarray formed by consecutive integers.
Given an integer array, find the largest subarray formed by consecutive integers. The subarray should contain all distinct values.
Input: { 2, 0, 2, 1, 4, 3, 1, 0 }
Output: The largest subarray is { 0, 2, 1, 4, 3 }
It is asked for subarray–> we need consecutive numbers
For a subarray to contain consecutive integers,
The difference between the maximum and minimum element in it should be exactly equal to the subarray’s length minus one.
All elements in the array should be distinct (we can check this by inserting the elements in a set or using a visited array).
we need two functions:
Function to check if subarray A[i…j] is formed by consecutive integers.
# Here, min and max denote the minimum and maximum element in the subarray.
O(n3)
________Code
def isConsecutive(A, i, j, min, max):
# for a list to contain consecutive integers, the difference
# between the maximum and minimum element in it should be exactly `j-i`
if max - min != j - i:
return False
# create a visited list (we can also use a set)
visited = [False] * (j - i + 1)
# traverse the sublist and check if each element appears
# only once
for k in range(i, j + 1):
# if the element is seen before, return false
if visited[A[k] - min]:
return False
# mark the element as seen
visited[A[k] - min] = True
# we reach here when all elements in the list are distinct
return True
Find the largest sublist formed by consecutive integers
def findMaxSublist(A):
length = 1 start = end = 0 # consider each sublist formed by `A[i…j]`
# `i` denotes the beginning of the sublist
for i in range(len(A) - 1):
# stores the minimum and maximum element formed by `A[i…j]`
min_val = A[i]
max_val = A[i]
# `j` denotes the end of the sublist
for j in range(i + 1, len(A)):
# update the minimum and maximum elements of the sublist
min_val = min(min_val, A[j])
max_val = max(max_val, A[j])
# check if `A[i…j]`is formed by consecutive integers
if isConsecutive(A, i, j, min_val, max_val):
if length < max_val - min_val + 1:
length = max_val - min_val + 1
start = i
end = j
# print the maximum length sublist
print("The largest sublist is", (start, end))
# Find the largest sublist formed by consecutive integers def findMaxSublist(A):
length = 1 start = end = 0 # consider each sublist formed by `A[i…j]`
# `i` denotes the beginning of the sublist
for i in range(len(A) - 1):
# stores the minimum and maximum element formed by `A[i…j]`
min_val = A[i]
max_val = A[i]
# `j` denotes the end of the sublist
for j in range(i + 1, len(A)):
# update the minimum and maximum elements of the sublist
min_val = min(min_val, A[j])
max_val = max(max_val, A[j])
# check if `A[i…j]`is formed by consecutive integers
if isConsecutive(A, i, j, min_val, max_val):
if length < max_val - min_val + 1:
length = max_val - min_val + 1
start = i
end = j
# print the maximum length sublist
print("The largest sublist is", (start, end))
Find maximum length subarray having a given sum
Given an integer array, find the maximum length subarray having a given sum.
A naive solution is to consider all subarrays and find their sum. If the subarray sum is equal to the given sum, update the maximum length subarray. The time complexity of the naive solution is O(n3) as there are n2 subarrays in an array of size n, and it takes O(n) time to find the sum of its elements. We can optimize the method to run in O(n2) time by calculating the subarray sum in constant time.
However,
We can use a map to solve this problem in linear time. The idea is to create an empty map to store the first subarray’s ending index, having a given sum. We traverse the given array and maintain the sum of elements seen so far.
If the target is seen for the first time, insert the sum with its index into the map.
If target-S is seen before, there is a subarray with the given sum that ends at the current index, and we update the maximum length subarray having sum S if the current subarray has more length.
https://www.techiedelight.com/find-maximum-length-sub-array-having-given-sum/
********************************************** # Find maximum length sublist with sum `S` present in a given list def findMaxLenSublist(nums, S):
# create an empty dictionary to store the ending index of the first
# sublist having some sum
d = {}
# insert (0, -1) pair into the set to handle the case when a
# sublist with sum `S` starts from index 0
d[0] = -1
target = 0
# `length` stores the maximum length of sublist with sum `S`
length = 0
# stores ending index of the maximum length sublist having sum `S`
ending_index = -1
# traverse the given list
for i in range(len(nums)):
# target of elements so far
target += nums[i]
# if the sum is seen for the first time, insert the sum with its
# into the dictionary
if target not in d:
d[target] = i
# update length and ending index of the maximum length sublist
# having sum `S`
if target - S in d and length < i - d[target - S]:
length = i - d[target - S]
ending_index = i
# print the sublist
print((ending_index - length + 1, ending_index))
if __name__ == ‘__main__’:
nums = [5, 6, -5, 5, 3, 5, 3, -2, 0] target = 8 findMaxLenSublist(nums, target)
Find the largest subarray having an equal number of 0’s and 1’s
Given a binary array containing 0’s and 1’s, find the largest subarray with equal numbers of 0’s and 1’s.
A naive solution would be to consider all subarrays and, for each subarray, count the total number of 0’s and 1’s present. If the subarray contains an equal number of 0’s and 1’s, update the largest subarray if required. The time complexity of the naive solution is O(n3) as there are n2 subarrays in an array of size n, and it takes O(n) time to find count 0’s and 1’s. We can optimize the method to run in O(n2) time by calculating the count of 0’s and 1’s in constant time.
We can use the map to solve this problem in linear time. The idea is to replace 0 with -1 and find out the largest subarray with a sum of 0. To find the largest subarray with a sum of 0, create an empty map that stores the first subarray’s ending index having a given sum. Then traverse the given array and maintain the sum of elements seen so far.
If the sum is seen for the first time, insert the sum with its index into the map.
If the sum is seen before, there exists a subarray with a sum of 0, which ends at the current index, and update the largest subarray if the current subarray has more length.
################## code########### def findLargestSublist(nums):
# create an empty dictionary to store the ending index of the first
# sublist having some sum
d = {}
# insert (0, -1) pair into the set to handle the case when a
# sublist with zero-sum starts from index 0
d[0] = -1
# `length` stores the maximum length of sublist with zero-sum
length = 0
# stores ending index of the largest sublist having zero-sum
ending_index = -1
total = 0
# Traverse through the given list
for i in range(len(nums)):
# sum of elements so far (replace 0 with -1)
total += -1 if (nums[i] == 0) else 1
# if the sum is seen before
if total in d:
# update length and ending index of largest sublist having zero-sum
if length < i - d.get(total):
length = i - d.get(total)
ending_index = i
# if the sum is seen for the first time, insert the sum with its
# index into the dictionary
else:
d[total] = i
# print the sublist if present
if ending_index != -1:
print((ending_index - length + 1, ending_index))
else:
print('No sublist exists')
if __name__ == ‘__main__’:
nums = [0, 0, 1, 0, 1, 0, 0] findLargestSublist(nums)
Sort an array of 0’s, 1’s, and 2’s (Dutch National Flag Problem)
Given an array containing only 0’s, 1’s, and 2’s, sort it in linear time and using constant space.
A simple solution would be to perform a counting sort. We count the total number of 0’s, 1’s, and 2’s and then put them in the array in their correct order. The time complexity of this solution is O(n), where n is the size of the input. However, this requires two traversals of the array.
We can rearrange the array in a single traversal using an alternative linear-time partition routine that separates the values into three groups:
The values less than the pivot,
The values equal to the pivot, and
The values greater than the pivot.
The time complexity of the above solution is O(n) and doesn’t require any extra space, where n is the size of the input.
********* code******************************* # Utility function to swap elements `A[i]` and `A[j]` in the list def swap(A, i, j):
temp = A[i] A[i] = A[j] A[j] = temp
# Linear time partition routine to sort a list containing 0, 1, and 2. # It is similar to 3–way partitioning for the Dutch national flag problem. def threeWayPartition(A):
start = mid = 0
pivot = 1
end = len(A) - 1
while mid <= end:
if A[mid] < pivot: # current element is 0
swap(A, start, mid)
start = start + 1
mid = mid + 1
elif A[mid] > pivot: # current element is 2
swap(A, mid, end)
end = end - 1
else: # current element is 1
mid = mid + 1
if __name__ == ‘__main__’:
A = [0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0] threeWayPartition(A) print(A)
In-place merge two sorted arrays
Given two sorted arrays, X[] and Y[] of size m and n each, merge elements of X[] with elements of array Y[] by maintaining the sorted order, i.e., fill X[] with the first m smallest elements and fill Y[] with remaining elements.
Input:
X[] = { 1, 4, 7, 8, 10 }
Y[] = { 2, 3, 9 }
Output:
X[] = { 1, 2, 3, 4, 7 }
Y[] = { 8, 9, 10 }
The idea is simple. Consider each array element X[] and ignore it if it is already in the correct order (i.e., the element smallest among all remaining elements); otherwise, swap it with the smallest element, which happens to be the first element of Y[]. After swapping, move the element (now present at Y[0]) to its correct position in Y[] to maintain the sorted order.
The time complexity of the above solution is O(m.n), where m is the size of the first array and n is the size of the second array. The solution doesn’t require any extra space. The problem, in fact, can be solved in linear time and constant space. This approach is highly complicated and is discussed here.
###### code############ # Function to in-place merge two sorted lists `X` and `Y` # invariant: `X` and `Y` are sorted at any point def merge(X, Y):
m = len(X) n = len(Y)
# Consider each element `X[i]` of list `X[]` and ignore the element if it is
# already in the correct order; otherwise, swap it with the next smaller
# element, which happens to be the first element of `Y[]`.
for i in range(m):
# compare the current element of `X[]` with the first element of `Y[]`
if X[i] > Y[0]:
# swap `X[i] with `Y[0]`
temp = X[i]
X[i] = Y[0]
Y[0] = temp
first = Y[0]
# move `Y[0]` to its correct position to maintain the sorted
# order of `Y[]`. Note: `Y[1…n-1]` is already sorted
k = 1
while k < n and Y[k] < first:
Y[k - 1] = Y[k]
k = k + 1
Y[k - 1] = first
if __name__ == ‘__main__’:
X = [1, 4, 7, 8, 10]
Y = [2, 3, 9]
merge(X, Y)
print("X:", X)
print("Y:", Y)
Merge two arrays by satisfying given constraints
Given two sorted arrays X[] and Y[] of size m and n each where m >= n and X[] has exactly n vacant cells, merge elements of Y[] in their correct position in array X[], i.e., merge (X, Y) by keeping the sorted order.
Input:
X[] = { 0, 2, 0, 3, 0, 5, 6, 0, 0 }
Y[] = { 1, 8, 9, 10, 15 }
The vacant cells in X[] is represented by 0
Output:
X[] = { 1, 2, 3, 5, 6, 8, 9, 10, 15 }
The idea is simple – move non-empty elements of X[] at the beginning of X[] and then merge X[] with Y[] starting from the end. The merge process is similar to the merge routine of the merge sort algorithm.
O(m+n)
##############code###### ## merge with constrain
def rearrange(X, Y):
if len(X)==0:
return;
## movens non empty elemnt of x and count the number of non zero of X
k = 0 ## for saving the space of non zero
for i in range(len(X)):
if X[i]:
X[k] =X[i]
k+=1
merge(X,Y,k-1, len(Y)-1 )
def merge(X, Y, m, n):
l = m+n+1
## the new array will be filled out from th end which is l
while m>=0 and n>=0:
if X[m]> Y[n]:
X[l] = X[m]
l-=1
m-=1
else:
X[l] = Y[n]
l-=1
n-=1
while n>=0:
X[l] = Y[n]
l-=1
n-=1
for i in range(len(Y)):
Y[i] = 0
if __name__ == ‘__main__’:
# vacant cells in `X[]` is represented by 0
X = [0, 2, 0, 3, 0, 5, 6, 0, 0]
Y = [1, 8, 9, 10, 15]
''' Validate input before calling `rearrange()`
1. Both lists `X[]` and `Y[]` should be sorted (ignore 0's in `X[]`)
2. Size of list `X[]` >= size of list `Y[]` (i.e., `m >= n`)
3. Total number of vacant cells in list `X[]` = size of list `Y[]` '''
# merge `Y` into `X`
rearrange(X, Y)
# print merged list
print(X)
Find the index of 0 to be replaced to get the maximum length sequence of continuous ones
Given a binary array, find the index of 0 to be replaced with 1 to get the maximum length sequence of continuous ones.
the problem can solved in O(n) time. The idea is to keep track of three indexes, current index (curr), previous zero index (prev_zero) and previous to previous zero index (prev_prev_zero).
Traverse the array, if current element is 0, calculate the difference between curr and prev_prev_zero (This difference minus one is the number of 1s around the prev_zero). If the difference between curr and prev_prev_zero is more than maximum so far, then update the maximum. Finally return index of the prev_zero with maximum difference.
def maxOnesIndex(arr,n):
# for maximum number of 1 around a zero
max_count = 0
# for storing result
max_index =0
# index of previous zero
prev_zero = -1
# index of previous to previous zero
prev_prev_zero = -1
# Traverse the input array
for curr in range(n):
# If current element is 0,
# then calculate the difference
# between curr and prev_prev_zero
if (arr[curr] == 0):
# Update result if count of
# 1s around prev_zero is more
if (curr - prev_prev_zero > max_count):
max_count = curr - prev_prev_zero
max_index = prev_zero
# Update for next iteration
prev_prev_zero = prev_zero
prev_zero = curr
# Check for the last encountered zero
if (n-prev_prev_zero > max_count):
max_index = prev_zero
return max_index
Driver program
arr = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1] n = len(arr)
print(“Index of 0 to be replaced is “,
maxOnesIndex(arr, n))
Find the maximum product of two integers in an array
Given an integer array, find the maximum product of two integers in it.
For example, consider array {-10, -3, 5, 6, -2}. The maximum product is the (-10, -3) or (5, 6) pair.
A naive solution is to consider every pair of elements and calculate their product. Update the maximum product found so far if the product of the current pair is greater. Finally, print the elements involved in the maximum product. O(n2) ####### code#######
import sys
# A naive solution to finding the maximum product of two integers in a list def findMaximumProduct(A):
# base case
if len(A) < 2:
return
max_product = -sys.maxsize
max_i = max_j = -1
# consider every pair of elements
for i in range(len(A) - 1):
for j in range(i + 1, len(A)):
# update the maximum product if required
if max_product < A[i] * A[j]:
max_product = A[i] * A[j]
(max_i, max_j) = (i, j)
print("Pair is", (A[max_i], A[max_j]))
if __name__ == ‘__main__’:
A = [-10, -3, 5, 6, -2] findMaximumProduct(A)
_____________________
O(nlogn)
The time complexity can be improved by sorting the array. Then the result is the maximum of the following:
The product of maximum and second maximum integer in the array (i.e., the last two elements in a sorted array).
The product of minimum and second minimum integers in the array (i.e., the first two elements in the sorted array).
# A naive solution to finding the maximum product of two integers in a list def findMaximumProduct(A):
# `n` is the length of the list
n = len(A)
# base case
if n < 2:
return
# sort list in ascending order
A.sort()
# choose the maximum of the following:
# 1. Product of the first two elements or
# 2. Product of the last two elements.
if (A[0] * A[1]) > (A[n - 1] * A[n - 2]):
print("Pair is", (A[0], A[1]))
else:
print("Pair is", (A[n - 1], A[n - 2]))
if __name__ == ‘__main__’:
A = [-10, -3, 5, 6, -20] findMaximumProduct(A)
__________________________
We can solve this problem in linear time as we need the only maximum, second maximum, minimum, and second minimum elements to solve this problem. We can compute all these in only a single traversal of the array, which accounts for O(n) time complexity.
import sys
# Function to find the maximum product of two integers in a list def findMaximumProduct(A):
# to store the maximum and second maximum element in a list
max1 = A[0]
max2 = -sys.maxsize
# to store the minimum and second minimum element in a list
min1 = A[0]
min2 = sys.maxsize
for i in range(1, len(A)):
# if the current element is more than the maximum element,
# update the maximum and second maximum element
if A[i] > max1:
max2 = max1
max1 = A[i]
# if the current element is less than the maximum but greater than the
# second maximum element, update the second maximum element
elif A[i] > max2:
max2 = A[i]
# if the current element is less than the minimum element,
# update the minimum and the second minimum
if A[i] < min1:
min2 = min1
min1 = A[i]
# if the current element is more than the minimum but less than the
# second minimum element, update the second minimum element
elif A[i] < min2:
min2 = A[i]
# otherwise, ignore the element
# choose the maximum of the following:
# 1. Product of the maximum and second maximum element or
# 2. Product of the minimum and second minimum element
if max1 * max2 > min1 * min2:
print("Pair is", (max1, max2))
else:
print("Pair is", (min1, min2))
if __name__ == ‘__main__’:
A = [-10, -3, 5, 6, -2] findMaximumProduct(A)
what is Fisher–Yates shuffle?
is an algorithm to generate random permutations. It takes time proportional to the total number of items being shuffled and shuffles them in place. The algorithm swaps the element at each iteration at random among all remaining unvisited indices, including the element itself.
Here’s the complete algorithm:
— To shuffle an array ‘a’ of ‘n’ elements:
for i from n-1 down to 1 do
j = random integer such that 0 <= j <= i
exchange a[j] and a[i]
Shuffle an array using Fisher–Yates shuffle algorithm
Given an integer array, in-place shuffle it. The algorithm should produce an unbiased permutation, i.e., every permutation is equally likely.
Fisher–Yates shuffle is an algorithm to generate random permutations. It takes time proportional to the total number of items being shuffled and shuffles them in place. The algorithm swaps the element at each iteration at random among all remaining unvisited indices, including the element itself.
O(n)
############# Code from random import randrange
def swap(A, i, j):
temp = A[i]
A[i] = A[j]
A[j] = temp
def inplace_shuffle(A):
for i in reversed(range(1,len(A))):
j = randrange(i+1)
swap(A, j, i)
if __name__ == ‘__main__’:
A = [1, 2, 3, 4, 5, 6] inplace_shuffle(A)
# print the shuffled list
print(A)
Rearrange an array with alternate high and low elements
Rearrange an array with alternate high and low elements
Input: {9, 6, 8, 3, 7}
Output: {6, 9, 3, 8, 7}
Solution 1:
RearrangeArray(arr[], n)
Sort the array in ascending order.
Take two index variables i and j to that point to two endpoints of the array (i.e., i = 0 and j = n-1).
Create an auxiliary array A[] and initialize an index k with 0.
Do while (i < j)
A[k++] = arr[i++]
A[k++] = arr[j–]
Print A[].
O(nlogn)
############
Solution 2:
without sorting.
An efficient solution doesn’t involve sorting the array or the use of extra space. The idea is to start from the second array element and increment the index by 2 for each loop’s iteration. If the last element is greater than the current element, swap the elements. Similarly, if the next element is greater than the current element, swap both elements. At the end of the loop, we will get the desired array that satisfies given constraints.
######## coding # Utility function to swap elements `A[i]` and `A[j]` in the list def swap(A, i, j):
temp = A[i] A[i] = A[j] A[j] = temp
# Function to rearrange the list such that every second element # of the list is greater than its left and right elements def rearrangeArray(A):
# start from the second element and increment index
# by 2 for each iteration of the loop
for i in range(1, len(A), 2):
# if the previous element is greater than the current element,
# swap the elements
if A[i - 1] > A[i]:
swap(A, i - 1, i)
# if the next element is greater than the current element,
# swap the elements
if i + 1 < len(A) and A[i + 1] > A[i]:
swap(A, i + 1, i)
if __name__ == ‘__main__’:
A = [9, 6, 8, 3, 7] re_arrange(A)
# print output list
print(A)
Find equilibrium index of an array
Given an integer array, find the equilibrium index in it.
For an array A consisting n elements, index i is an equilibrium index if the sum of elements of subarray A[0…i-1] is equal to the sum of elements of subarray A[i+1…n-1]. i.e.
(A[0] + A[1] + … + A[i-1]) = (A[i+1] + A[i+2] + … + A[n-1]), where 0 < i < n-1
Similarly, 0 is an equilibrium index if A[1] + A[2] + … + A[n-1] sums to 0 and n-1 is an equilibrium index if A[0] + A[1] + … + A[n-2] sums to 0.
A naive solution would be to calculate the sum of elements to the left and the sum of elements to each array element’s right. If the left subarray sum is the same as the right subarray sum for an element, print its index. The time complexity of this solution is O(n2), where n is the size of the input
- Linear-time Solution
We can solve this problem in linear time by using extra space. The idea is to create an auxiliary array left[], where left[i] stores a sum of elements of the subarray A[0…i-1]. After left[] is filled, traverse the array from right to left and update them right subarray sum for each element encountered. Now, if the sum of elements of the left subarray A[0…i-1] is equal to the sum of elements of the right subarray A[i+1…n) for element A[i], we have found the equilibrium index at I.
############coding # Function to find the equilibrium index of a list def findEquilibriumIndex(A):
# `left[i]` stores the sum of elements of sublist `A[0…i-1]`
left = [0] * len(A)
# traverse the list from left to right
for i in range(1, len(A)):
left[i] = left[i - 1] + A[i - 1]
# `right` stores the sum of elements of sublist `A[i+1…n)`
right = 0
# maintain a list of indices
indices = []
# traverse the list from right to left
for i in reversed(range(len(A))):
''' if the sum of elements of sublist `A[0…i-1]` is equal to
the sum of elements of sublist `A[i+1…n)` i.e.
`(A[0] + … + A[i-1]) = (A[i+1] + A[i+2] + … + A[n-1])` '''
if left[i] == right:
indices.append(i)
# new right is `A[i] + (A[i+1] + A[i+2] + … + A[n-1])`
right += A[i]
print("Equilibrium Index found at", indices)
if __name__ == ‘__main__’:
A = [0, -3, 5, -4, -2, 3, 1, 0] findEquilibriumIndex(A)
Boyer–Moore Majority Vote Algorithm
Given an integer array containing duplicates, return the majority element if present. A majority element appears more than n/2 times, where n is the array size.
For example, the majority element is 2 in array {2, 8, 7, 2, 2, 5, 2, 3, 1, 2, 2}.
Approach 1:
O(N)
Linear-time Solution We can use hashing to solve this problem in linear time. The idea is to store each element’s frequency in a map and return it if its frequency becomes more than n/2. If no such element is present, then the The majority element doesn’t exist in the array, and return -1. ### coding### # Function to find the majority element present in a given list def findMajorityElement(nums):
# create an empty `HashMap`
d = {}
# store each element's frequency in a dictionary
for i in nums:
d[i] = d.get(i, 0) + 1
# return the element if its count is more than `n/2`
for key, value in d.items():
if value > len(nums) / 2:
return key
# no majority element is present
return -1
if __name__ == ‘__main__’:
# assumption: valid input (majority element is present)
nums = [1, 8, 7, 4, 1, 2, 2, 2, 2, 2, 2]
result = findMajorityElement(nums)
if result != -1:
print('The majority element is', result)
else:
print('The majority element doesn\'t exist')
Download Run Code
Output:
The majority element is 2
The time complexity of the above solution is O(n) and requires O(n) extra space.
- Boyer–Moore majority vote algorithm
We can find the majority element using linear time and constant space using the Boyer–Moore majority vote algorithm. The algorithm can be expressed in pseudocode as the following steps:
Initialize an element m and a counter i = 0
for each element x of the input sequence:
if i = 0, then
assign m = x and i = 1
else
if m = x, then assign i = i + 1
else
assign i = i – 1
return m
The algorithm processes each element of the sequence, one at a time. When processing an element x,
If the counter is 0, set the current candidate to x, and set the counter to 1.
If the counter is non-zero, increment or decrement it according to whether x is a current candidate.
At the end of this process, if the sequence has a majority, it will be the element stored by the algorithm. If there is no majority element, the algorithm will not detect that fact and may output the wrong element. In other words, the Boyer–Moore majority vote algorithm produces correct results only when the majority element is present in the input.
The algorithm can be implemented as follows in C, Java, and Python. It is recommended to modify the algorithm to verify if the returned element is, in fact, a majority element or not.
# Function to find the majority element present in a given list def findMajorityElement(nums):
# `m` stores the majority element (if present)
m = -1
# initialize counter `i` with 0
i = 0
# do for each element `nums[j]` in the list
for j in range(len(nums)):
# if counter `i` becomes 0
if i == 0:
# set the current candidate to `nums[j]`
m = nums[j]
# reset the counter to 1
i = 1
# otherwise, increment the counter if `nums[j]` is a current candidate
elif m == nums[j]:
i = i + 1
# otherwise, decrement the counter if `nums[j]` is a current candidate
else:
i = i - 1
return m
if __name__ == ‘__main__’:
# assumption: valid input (majority element is present)
nums = [1, 8, 7, 4, 1, 2, 2, 2, 2, 2, 2]
print('The majority element is', findMajorityElement(nums))
_______________________________-
Approach 2
We can improve worst-case time complexity to O(n.log(n)) by sorting the array and then perform a binary search for each element’s first and last occurrence. If the difference between first and last occurrence is more than n/2, the The majority element is found.
Move all zeros present in an array to the end
Given an integer array, move all zeros present in it to the end. The solution should maintain the relative order of items in the array and should not use constant space.
The idea is simple – if the current element is non-zero, place the element at the next available position in the array. After all elements in the array are processed, fill all remaining indices by 0. This approach is demonstrated below in
############## code######### # Function to move all zeros present in the list to the end def reorder(A):
# `k` stores the index of the next available position
k = 0
# do for each element
for i in A:
# if the current element is non-zero, put the element at the
# next free position in the list
if i:
A[k] = i
k = k + 1
# move all 0's to the end of the list (remaining indices)
for i in range(k, len(A)):
A[i] = 0
if __name__ == ‘__main__’:
A = [6, 0, 8, 2, 3, 0, 4, 0, 1] reorder(A) print(A)
