# Linear time iterate over all itemsarr = [12,23,56,87,14] # n = 5for num in arr:# O(n * 1) ==> O(n)print(num)# O(1)for num in arr:# O(n * 1) ==> O(n)print(num)# O(1)# O(n) + O(1) => O(n)# O(n * 1) + O(n * 1) + O(1)# O(2n) + O(1) => O(n) + O(1) => O(n)# constant time lookupprint(arr[3])# O(1)# quadratic time nested iterationfor x in arr:# O(n)for y in arr:# O(n) => O(n^2)for z in arr:# O(n^3)print(x, y, z)# O(1) => O(1 * n^2)# O(n^2) + O(n) + O(1 * n^2)# O(2n^2) + O(n) => O(n^2) + O(n^2)# O(n^2) => O(n^3)# 10 * 10 * 10 => 1000# 100 * 100 * 100 => 1000000# can we do better?
Arrays
In an array of arrays, e.g. given [[], [1, 2, 3], [4, 5], [], [], [6, 7], [8], [9, 10], [], []], print: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
Implement an iterator that supports hasNext(), next() and remove() methods.
Given a list of item prices, find all possible combinations of items that sum a particular value K.
Paginate an array with constraints, such as skipping certain items.
Implement a circular buffer using an array.
Given array of arrays, sort them in ascending order.
Given an array of integers, print out a histogram using the said array; include a base layer (all stars)
E.g. [5, 4, 0, 3, 4, 1]
*
** *
** **
** **
** ***
******
Given an array and an index, find the product of the elements of the array except the element at that index.
Given a set of rectangles represented by a height and an interval along the y-axis, determine the size of its union.
Given 2 separate arrays, write a method to find the values that exist in both arrays and return them.
Given an array of integers find whether there is a sub-sequence that sums to 0 and return it.
E.g. [1, 2, -3, 1] => [1, 2, -3] or [2, -3, 1].
Given an input array and another array that describes a new index for each element, mutate the input array so that each element ends up in their new index. Discuss the runtime of the algorithm and how you can be sure there would not be any infinite loops.
Given an array of non-negative numbers, find continuous subarray with sum to S.
Given an array of numbers list out all quadruplets that sum to 0. Do so with a running time of less than O(n^4).
Given an array of integers, move all the zeroes to the end while preserving the order of the other elements. You have to do it in-place and are not allowed to use any extra storage.
Given an array of integers, find the subarray with the largest sum. Can you do it in linear time.
Maximum subarray sum problem.
You have an array with the heights of an island (at point 1, point 2 etc) and you want to know how much water would remain on this island (without flowing away).
Trapping rain water question.
Given an array containing only digits 0-9, add one to the number and return the array.
E.g. Given [1, 4, 2, 1] which represents 1421, return [1, 4, 2, 2] which represents 1422.
Find the second maximum value in an array.
Given an array, find the longest arithmetic progression.
Rotate an array by an offset of k.
Remove duplicates in an unsorted array where the duplicates are at a distance of k or less from each other.
Given an unsorted list of integers, return true if the list contains any duplicates within k indices of each element. Do it faster than O(n^2).
Given an unsorted list of integers, return true if the list contains any fuzzy duplicates within k indices of each element. A fuzzy duplicate is another integer within d of the original integer. Do it faster than O(n^2).
E.g. If d = 4, then 6 is a fuzzy duplicate of 3 but 8 is not.
Say you have an unordered list of numbers ranging from 1 to n, and one of the numbers is removed, how do you find that number? What if two numbers are removed?
Given an array of string, find the duplicated elements.
Given an array of integers where every value appears twice except one, find the single, non-repeating value. Follow up: do so with O(1) space.
E.g., [2, 5, 3, 2, 1, 3, 4, 5, 1] returns 4, because it is the only value that appears in the array only once.
# Python Program to demonstrate creation of Array using array creationsimport array as arrprint("INTEGER ARRAY OPERATIONS:")size =int(input(" Enter the size of Array: "))# creating an array with integer typelst =list()for i inrange(size): lst.append(int(input("Enter the Integer Element:")))n = arr.array(lst)# printing arraydefpr(n):print("The new integer array is : ", end=" ")for i inrange(len(n)):print(n[i], end =", ")print()defadd(n,j):print("The Array before adding: ", end=" ")for i inrange(len(n)):print(n[i], end=", ")print()#Append() method n.append(j)print("The Array After adding: ", end=" ")for i inrange(len(n)):print(n[i], end=", ")print()defadde(n,j,p):print("The Array before adding: ", end=" ")for i inrange(len(n)):print(n[i], end=", ")print()#insert() method n.insert(p,j)print("The Array After adding: ", end=" ")for i inrange(len(n)):print(n[i], end=", ")print()defpp(n,j):if n:print("The Array before Popping: ", end=" ")for i inrange(len(n)):print(n[i], end=", ")print()# pop() method n.pop(j)print("The Array After Popping: ", end=" ")for i inrange(len(n)):print(n[i], end=", ")print()else:print("Array Empty")defprt(n,j):if n:if j inrange(len(n)):print("The Array before Removing: ", end=" ")for i inrange(len(n)):print(n[i], end=", ")print()#remove Method n.remove(j)print("The Array After Removing: ", end=" ")for i inrange(len(n)):print(n[i], end=", ")print()else:print("Index Out of Bound")else:print("Array Empty")#Driver codeflag =1while(flag):print()print("1.Print Array\n2.Add Element using append()\n3.Add Element using insert()\n4.Pop() Element\n5.Remove Element at position\n6.Exit\n") option =int(input("Enter the option :"))if option ==1:pr(n)elif option ==2: i =int(input("Enter the Element to be added: "))add(n,i)elif option ==3: p =int(input("Enter the position to add element:")) i =int(input("Enter the Element: "))adde(n, i, p)elif option ==4: i =int(input("Enter the Index position To be popped: "))pp(n, i)elif option ==5: i =int(input("Enter the Element Position To be Removed: "))prt(n, i)elif option ==6: flag =0
"""Given a list lst and a number N, create a new listthat contains each number of the list at most N times without reordering.For example if N = 2, and the input is [1,2,3,1,2,1,2,3], you take [1,2,3,1,2], drop the next [1,2] since this would lead to 1 and 2 being in the result 3 times, and then take 3, which leads to [1,2,3,1,2,3]"""import collections# Time complexity O(n^2)defdelete_nth_naive(array,n): ans = []for num in array:if ans.count(num)< n: ans.append(num)return ans# Time Complexity O(n), using hash tables.defdelete_nth(array,n): result = [] counts = collections.defaultdict(int)# keep track of occurrencesfor i in array:if counts[i]< n: result.append(i) counts[i]+=1return result"""Implement Flatten Arrays.Given an array that may contain nested arrays,produce a single resultant array."""from collections.abc import Iterable# return listdefflatten(input_arr,output_arr=None):if output_arr isNone: output_arr = []for ele in input_arr:ifnotisinstance(ele, str)andisinstance(ele, Iterable):flatten(ele, output_arr)# tail-recursionelse: output_arr.append(ele)# produce the resultreturn output_arr# returns iteratordefflatten_iter(iterable):""" Takes as input multi dimensional iterable and returns generator which produces one dimensional output. """for element in iterable:ifnotisinstance(element, str)andisinstance(element, Iterable):yield fromflatten_iter(element)else:yield element"""There is a parking lot with only one empty spot. Given the initial stateof the parking lot and the final state. Each step we are only allowed tomove a carout of its place and move it into the empty spot.The goal is to find out the least movement needed to rearrangethe parking lot from the initial state to the final state.Say the initial state is an array:[1, 2, 3, 0, 4],where 1, 2, 3, 4 are different cars, and 0 is the empty spot.And the final state is[0, 3, 2, 1, 4].We can swap 1 with 0 in the initial array to get [0, 2, 3, 1, 4] and so on.Each step swap with 0 only.Edit:Now also prints the sequence of changes in states.Output of this example :-initial: [1, 2, 3, 0, 4]final: [0, 3, 2, 1, 4]Steps = 4Sequence : 0 2 3 1 42 0 3 1 42 3 0 1 40 3 2 1 4"""defgarage(initial,final): initial = initial[::]# prevent changes in original 'initial' seq = [] # list of each step in sequence steps =0while initial != final: zero = initial.index(0)if zero != final.index(0):# if zero isn't where it should be, car_to_move = final[zero]# what should be where zero is, pos = initial.index(car_to_move)# and where is it? initial[zero], initial[pos]= initial[pos], initial[zero]else:for i inrange(len(initial)):if initial[i]!= final[i]: initial[zero], initial[i]= initial[i], initial[zero]break seq.append(initial[::]) steps +=1return steps, seq# e.g.: 4, [{0, 2, 3, 1, 4}, {2, 0, 3, 1, 4},# {2, 3, 0, 1, 4}, {0, 3, 2, 1, 4}]"""thus:1 2 3 0 4 -- zero = 3, true, car_to_move = final[3] = 1, pos = initial.index(1) = 0, switched [0], [3]0 2 3 1 4 -- zero = 0, f, initial[1] != final[1], switched 0,12 0 3 1 4 -- zero = 1, t, car_to_move = final[1] = 3, pos = initial.index(3) = 2, switched [1], [2]2 3 0 1 4 -- zero = 2, t, car_to_move = final[2] = 2, pos = initial.index(2) = 0, switched [0], [2]0 3 2 1 4 -- initial == final"""from.delete_nth import*from.flatten import*from.garage import*from.josephus import*from.longest_non_repeat import*from.max_ones_index import*from.merge_intervals import*from.missing_ranges import*from.move_zeros import*from.plus_one import*from.rotate import*from.summarize_ranges import*from.three_sum import*from.trimmean import*from.top_1 import*from.two_sum import*from.limit import*from.n_sum import*"""There are people sitting in a circular fashion,print every third member while removing them,the next counter starts immediately after the member is removed.Print till all the members are exhausted.For example:Input: consider 123456789 members sitting in a circular fashion,Output: 369485271"""defjosephus(int_list,skip): skip = skip -1# list starts with 0 index idx =0 len_list =len(int_list)while len_list >0: idx = (skip + idx) % len_list # hash index to every 3rdyield int_list.pop(idx) len_list -=1"""Sometimes you need to limit array result to use. Such as you only need the value over 10 or, you need value under than 100. By use this algorithms, you can limit your array to specific valueIf array, Min, Max value was given, it returns array that contains values of given array which was larger than Min, and lower than Max. You need to give 'unlimit' to use only Min or Max.ex) limit([1,2,3,4,5], None, 3) = [1,2,3]Complexity = O(n)"""# tl:dr -- array slicing by valuedeflimit(arr,min_lim=None,max_lim=None): min_check =lambdaval: Trueif min_lim isNoneelse (min_lim <= val) max_check =lambdaval: Trueif max_lim isNoneelse (val <= max_lim)return [val for val in arr ifmin_check(val)andmax_check(val)]"""Given a string, find the length of the longest substringwithout repeating characters.Examples:Given "abcabcbb", the answer is "abc", which the length is 3.Given "bbbbb", the answer is "b", with the length of 1.Given "pwwkew", the answer is "wke", with the length of 3.Note that the answer must be a substring,"pwke" is a subsequence and not a substring."""deflongest_non_repeat_v1(string):""" Find the length of the longest substring without repeating characters. """if string isNone:return0dict={} max_length =0 j =0for i inrange(len(string)):if string[i]indict: j =max(dict[string[i]], j) dict[string[i]]= i +1 max_length =max(max_length, i - j +1)return max_lengthdeflongest_non_repeat_v2(string):""" Find the length of the longest substring without repeating characters. Uses alternative algorithm. """if string isNone:return0 start, max_len =0,0 used_char ={}for index, char inenumerate(string):if char in used_char and start <= used_char[char]: start = used_char[char]+1else: max_len =max(max_len, index - start +1) used_char[char]= indexreturn max_len# get functions of above, returning the max_len and substringdefget_longest_non_repeat_v1(string):""" Find the length of the longest substring without repeating characters. Return max_len and the substring as a tuple """if string isNone:return0,"" sub_string =""dict={} max_length =0 j =0for i inrange(len(string)):if string[i]indict: j =max(dict[string[i]], j) dict[string[i]]= i +1if i - j +1> max_length: max_length = i - j +1 sub_string = string[j : i +1]return max_length, sub_stringdefget_longest_non_repeat_v2(string):""" Find the length of the longest substring without repeating characters. Uses alternative algorithm. Return max_len and the substring as a tuple """if string isNone:return0,"" sub_string ="" start, max_len =0,0 used_char ={}for index, char inenumerate(string):if char in used_char and start <= used_char[char]: start = used_char[char]+1else:if index - start +1> max_len: max_len = index - start +1 sub_string = string[start : index +1] used_char[char]= indexreturn max_len, sub_string"""Find the index of 0 to be replaced with 1 to getlongest continuous sequenceof 1s in a binary array.Returns index of 0 to bereplaced with 1 to get longestcontinuous sequence of 1s.If there is no 0 in array, thenit returns -1.e.g.let input array = [1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1]If we replace 0 at index 3 with 1, we get the longest continuoussequence of 1s in the array.So the function return => 3"""defmax_ones_index(arr): n =len(arr) max_count =0 max_index =0 prev_zero =-1 prev_prev_zero =-1for curr inrange(n):# If current element is 0,# then calculate the difference# between curr and prev_prev_zeroif arr[curr]==0:if curr - prev_prev_zero > max_count: max_count = curr - prev_prev_zero max_index = prev_zero prev_prev_zero = prev_zero prev_zero = currif n - prev_prev_zero > max_count: max_index = prev_zeroreturn max_index"""In mathematics, a (real) interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set."""classInterval:""" A set of real numbers with methods to determine if other numbers are included in the set. Includes related methods to merge and print interval sets. """def__init__(self,start=0,end=0): self.start = start self.end = enddef__repr__(self):return"Interval ({}, {})".format(self.start, self.end)def__iter__(self):returniter(range(self.start, self.end))def__getitem__(self,index):if index <0:return self.end + indexreturn self.start + indexdef__len__(self):return self.end - self.startdef__contains__(self,item):if self.start >= item >= self.end:returnTruereturnFalsedef__eq__(self,other):if self.start == other.start and self.end == other.end:returnTruereturnFalsedefas_list(self):""" Return interval as list. """returnlist(self)@staticmethoddefmerge(intervals):""" Merge two intervals into one. """ out = []for i insorted(intervals, key=lambdai: i.start):if out and i.start <= out[-1].end: out[-1].end =max(out[-1].end, i.end)else: out += (i,)return out@staticmethoddefprint_intervals(intervals):""" Print out the intervals. """ res = []for i in intervals: res.append(repr(i))print("".join(res))defmerge_intervals(intervals):""" Merge intervals in the form of a list. """if intervals isNone:returnNone intervals.sort(key=lambdai: i[0]) out = [intervals.pop(0)]for i in intervals:if out[-1][-1] >= i[0]: out[-1][-1] =max(out[-1][-1], i[-1])else: out.append(i)return out"""Find missing ranges between low and high in the given array.Ex) [3, 5] lo=1 hi=10 => answer: [(1, 2), (4, 4), (6, 10)]"""defmissing_ranges(arr,lo,hi): res = [] start = lofor n in arr:if n == start: start +=1elif n > start: res.append((start, n -1)) start = n +1if start <= hi:# after done iterating thru array, res.append((start, hi))# append remainder to listreturn res"""Write an algorithm that takes an array and moves all of the zeros to the end,preserving the order of the other elements. move_zeros([false, 1, 0, 1, 2, 0, 1, 3, "a"]) returns => [false, 1, 1, 2, 1, 3, "a", 0, 0]The time complexity of the below algorithm is O(n)."""# False == 0 is Truedefmove_zeros(array): result = [] zeros =0for i in array:if i ==0andtype(i)!=bool:# not using `not i` to avoid `False`, `[]`, etc. zeros +=1else: result.append(i) result.extend([0] * zeros)return resultprint(move_zeros([False, 1, 0, 1, 2, 0, 1, 3, "a"]))"""Given an array of n integers, are there elements a, b, .. , n in numssuch that a + b + .. + n = target?Find all unique n-tuplets in the array which gives the sum of target.Example: basic: Given: n = 4 nums = [1, 0, -1, 0, -2, 2] target = 0, return [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] advanced: Given: n = 2 nums = [[-3, 0], [-2, 1], [2, 2], [3, 3], [8, 4], [-9, 5]] target = -5 def sum(a, b): return [a[0] + b[1], a[1] + b[0]] def compare(num, target): if num[0] < target: return -1 elif if num[0] > target: return 1 else: return 0 return [[-9, 5], [8, 4]](TL:DR) because -9 + 4 = -5"""defn_sum(n,nums,target,**kv):""" n: int nums: list[object] target: object sum_closure: function, optional Given two elements of nums, return sum of both. compare_closure: function, optional Given one object of nums and target, return -1, 1, or 0. same_closure: function, optional Given two object of nums, return bool. return: list[list[object]] Note: 1. type of sum_closure's return should be same as type of compare_closure's first param """defsum_closure_default(a,b):return a + bdefcompare_closure_default(num,target):""" above, below, or right on? """if num < target:return-1elif num > target:return1else:return0defsame_closure_default(a,b):return a == bdefn_sum(n,nums,target):if n ==2:# want answers with only 2 terms? easy! results =two_sum(nums, target)else: results = [] prev_num =Nonefor index, num inenumerate(nums):if prev_num isnotNoneandsame_closure(prev_num, num):continue prev_num = num n_minus1_results =n_sum( # recursive call n -1, nums[index +1 :], target - num # a # b # c )# x = n_sum( a, b, c ) # n_minus1_results = x n_minus1_results =append_elem_to_each_list(num, n_minus1_results) results += n_minus1_resultsreturnunion(results)deftwo_sum(nums,target): nums.sort() lt =0 rt =len(nums)-1 results = []while lt < rt: sum_ =sum_closure(nums[lt], nums[rt]) flag =compare_closure(sum_, target)if flag ==-1: lt +=1elif flag ==1: rt -=1else: results.append(sorted([nums[lt], nums[rt]])) lt +=1 rt -=1while lt <len(nums)andsame_closure(nums[lt -1], nums[lt]): lt +=1while0<= rt andsame_closure(nums[rt], nums[rt +1]): rt -=1return resultsdefappend_elem_to_each_list(elem,container): results = []for elems in container: elems.append(elem) results.append(sorted(elems))return resultsdefunion(duplicate_results): results = []iflen(duplicate_results)!=0: duplicate_results.sort() results.append(duplicate_results[0])for result in duplicate_results[1:]:if results[-1]!= result: results.append(result)return results sum_closure = kv.get("sum_closure", sum_closure_default) same_closure = kv.get("same_closure", same_closure_default) compare_closure = kv.get("compare_closure", compare_closure_default) nums.sort()returnn_sum(n, nums, target)"""Given a non-negative number represented as an array of digits,adding one to each numeral.The digits are stored big-endian, such that the most significantdigit is at the head of the list."""defplus_one_v1(digits):""" :type digits: List[int] :rtype: List[int] """ digits[-1]= digits[-1]+1 res = [] ten =0 i =len(digits)-1while i >=0or ten ==1: summ =0if i >=0: summ += digits[i]if ten: summ +=1 res.append(summ %10) ten = summ //10 i -=1return res[::-1]defplus_one_v2(digits): n =len(digits)for i inrange(n -1, -1, -1):if digits[i]<9: digits[i]+=1return digits digits[i]=0 digits.insert(0, 1)return digitsdefplus_one_v3(num_arr):for idx inreversed(list(enumerate(num_arr))): num_arr[idx[0]]= (num_arr[idx[0]]+1) %10if num_arr[idx[0]]:return num_arrreturn [1] + num_arr"""Rotate an array of n elements to the right by k steps.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."""defrotate_v1(array,k):""" Rotate the entire array 'k' times T(n)- O(nk) :type array: List[int] :type k: int :rtype: void Do not return anything, modify array in-place instead. """ array = array[:] n =len(array)for i inrange(k):# unused variable is not a problem temp = array[n -1]for j inrange(n -1, 0, -1): array[j]= array[j -1] array[0]= tempreturn arraydefrotate_v2(array,k):""" Reverse segments of the array, followed by the entire array T(n)- O(n) :type array: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ array = array[:]defreverse(arr,a,b):while a < b: arr[a], arr[b]= arr[b], arr[a] a +=1 b -=1 n =len(array) k = k % nreverse(array, 0, n - k -1)reverse(array, n - k, n -1)reverse(array, 0, n -1)return arraydefrotate_v3(array,k):if array isNone:returnNone length =len(array) k = k % lengthreturn array[length - k :]+ array[: length - k]"""Given a sorted integer array without duplicates,return the summary of its ranges.For example, given [0, 1, 2, 4, 5, 7], return [(0, 2), (4, 5), (7, 7)]."""defsummarize_ranges(array):""" :type array: List[int] :rtype: List[] """ res = []iflen(array)==1:return [str(array[0])] i =0while i <len(array): num = array[i]while i +1<len(array)and array[i +1]- array[i]==1: i +=1if array[i]!= num: res.append((num, array[i]))else: res.append((num, num)) i +=1return res"""Given an array S of n integers, are there three distinct elementsa, b, c in S such that a + b + c = 0?Find all unique triplets in the array which gives the sum of zero.Note: The solution set must not contain duplicate triplets.For example, given array S = [-1, 0, 1, 2, -1, -4],A solution set is:{ (-1, 0, 1), (-1, -1, 2)}"""defthree_sum(array):""" :param array: List[int] :return: Set[ Tuple[int, int, int] ] """ res =set() array.sort()for i inrange(len(array) -2):if i >0and array[i]== array[i -1]:continue l, r = i +1,len(array)-1while l < r: s = array[i]+ array[l]+ array[r]if s >0: r -=1elif s <0: l +=1else:# found three sum res.add((array[i], array[l], array[r]))# remove duplicateswhile l < r and array[l]== array[l +1]: l +=1while l < r and array[r]== array[r -1]: r -=1 l +=1 r -=1return res"""This algorithm receives an array and returns most_frequent_valueAlso, sometimes it is possible to have multiple 'most_frequent_value's,so this function returns a list. This result can be used to find a representative value in an array.This algorithm gets an array, makes a dictionary of it, finds the most frequent count, and makes the result list.For example: top_1([1, 1, 2, 2, 3, 4]) will return [1, 2](TL:DR) Get mathematical ModeComplexity: O(n)"""deftop_1(arr): values ={}# reserve each value which first appears on keys# reserve how many time each value appears by index number on values result = [] f_val =0for i in arr:if i in values: values[i]+=1else: values[i]=1 f_val =max(values.values())for i in values.keys():if values[i]== f_val: result.append(i)else:continuereturn result"""When make reliable means, we need to neglect best and worst values.For example, when making average score on athletes we need this option.So, this algorithm affixes some percentage to neglect when making mean.For example, if you suggest 20%, it will neglect the best 10% of valuesand the worst 10% of values.This algorithm takes an array and percentage to neglect. After sorted,if index of array is larger or smaller than desired ratio, we don'tcompute it.Compleity: O(n)"""deftrimmean(arr,per): ratio = per /200# /100 for easy calculation by *, and /2 for easy adaption to best and worst parts. cal_sum =0# sum value to be calculated to trimmean. arr.sort() neg_val =int(len(arr) * ratio) arr = arr[neg_val :len(arr)- neg_val]for i in arr: cal_sum += ireturn cal_sum /len(arr)"""Given an array of integers, return indices of the two numberssuch that they add up to a specific target.You may assume that each input would have exactly one solution,and you may not use the same element twice.Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return (0, 1)"""deftwo_sum(array,target): dic ={}for i, num inenumerate(array):if num in dic:return dic[num], ielse: dic[target - num]= ireturnNone
Extra-Array
# given array a and need to find value x# left and right correspond to initial indices of array a bounding the search# segment of array a above and below, respectivelydefbinary_search_recursive(a,x,left=0,right=(len(a)-1)):#"""Recursive Binary Search algorithm implemented using list indexing""" index = (left+right)//2if a[index]== x:return indexelif x > (a[right]) or x < a[left]:# first case where x is not in the list!return-1elif left == right:# case where search is complete and no value x not foundreturn-1elif left == right-1:# case where there are only two numbers left, check both! left = rightreturnbinary_search_recursive(a, x, left, right)elif a[index]< x: left = indexreturnbinary_search_recursive(a, x, left, right)elif a[index]> x: right = indexreturnbinary_search_recursive(a, x, left, right)
#Time complexity O(M*N)#Space Complexity O(M+N)#Method 1classSolution: #Function to return the count of number of elements in union of two arrays.defdoUnion(self,a,n,b,m): c=a+b c.sort() d=[]for i in c:if i notin d: d.append(i)else:passreturnlen(d)if__name__=='__main__': t=int(input())for _ inrange(t): n,m=[int(x)for x ininput().strip().split()] a=[int(x)for x ininput().strip().split()] b=[int(x)for x ininput().strip().split()] ob=Solution()print(ob.doUnion(a,n,b,m))#Time complexity O(M)+O(N)+O(Mlog(M)+Nlog(N))#Space Complexity O(n+m)#Method 2classSolution: #Function to return the count of number of elements in union of two arrays.defdoUnion(self,a,n,b,m): c=a+b c.sort()#O(Mlog(M))+O(Nlog(N)) sample_dict={}for i in c:#O(M)+O(N)if i in sample_dict.keys(): sample_dict[i]+=1else: sample_dict[i]=1returnlen([int(x) for x in sample_dict.values()])if__name__=='__main__': t=int(input())for _ inrange(t): n,m=[int(x)for x ininput().strip().split()] a=[int(x)for x ininput().strip().split()] b=[int(x)for x ininput().strip().split()] ob=Solution()print(ob.doUnion(a,n,b,m))
#rotation of an element by one stepdefleft_rotation(arr,d,n):for i inrange(d):rotate_by_one_step(arr,n)defrotate_by_one_step(arr,n): temp = arr[0]for i inrange(n-1): arr[i]= arr[i+1] arr[n-1]=tempdefprint_array(arr,n):for i inrange(n):print(arr[i])arr=[1,2,3,4,5]left_rotation(arr,2,5)print_array(arr,5)
classArray(object):def__init__(self,size,defaultValue=None): self.size = sizeif(defaultValue ==None): self.items =list()for i inrange(size): self.items.append(defaultValue)else: self.items =list()if(len(defaultValue)== size orlen(defaultValue)< size):for j inrange(len(defaultValue)):if(defaultValue[j]): self.items.append(defaultValue[j])for i inrange(len(defaultValue), size): self.items.append(None)else:print('Elements are more than the size specified')defmyLen(self): length =0for i in self.items:if i ==None:continueelse: length +=1return lengthdefinsertFirst(self,element):if (self.myLen()< self.size):for i inrange(self.myLen(), 0, -1): self.items[i]= self.items[i -1] self.items[0]= elementelse:print('Element index out of range')definsertAtIndex(self,index,element):if (self.myLen()< self.size):for i inrange(self.myLen(), index, -1): self.items[i]= self.items[i -1] self.items[index]= elementelse:print('Element index out of range')definsertAfterIndex(self,index,element):if (self.myLen()< self.size):for i inrange(self.myLen(), index +1, -1): self.items[i]= self.items[i -1] self.items[index +1]= elementelse:print('Element index out of range')definsertBeforeIndex(self,index,element):if (self.myLen()< self.size):for i inrange(self.myLen(), index -1, -1): self.items[i]= self.items[i -1] self.items[index -1]= elementelse:print('Element index out of range')defdelete(self,element):if element in self.items: Index = self.items.index(element) self.items[Index]=Noneelse:print('This element is not in the Array!')defsearch(self,element):if element in self.items: position =0for i inrange(self.myLen()):if(self.items[i]== element):breakelse: position +=1print('Element {} found at position {}'.format(element, position))else:print('This element is not in the Array!')if__name__=='__main__': myArray =Array(5, [1])print(myArray.items, myArray.myLen()) myArray.insertFirst(3)print(myArray.items, myArray.myLen()) myArray.insertAfterIndex(1,4)print(myArray.items, myArray.myLen()) myArray.insertBeforeIndex(3,5)print(myArray.items, myArray.myLen()) myArray.delete(5)print(myArray.items, myArray.myLen()) myArray.search(4)
Create Array Class
Now, first, let’s create a custom class named Array which implements all the above functionalities in it.
So now let’s define a constructor using init method in Python which accepts 2 arguments along with the self-object that is the size and the default value for Array elements.
Here, size is defined which is the static size of the array and the default value means the value assigned to elements while creating a new array.
Now what we need is that if the size is only initialized then we must initialize all elements to default Value that is None.
Otherwise, if both parameters are initialized, then initialize the list with these values the user passed as an argument.
If the length of the default value list is less than size, then initialize other elements to “None”.
If the length of the list passed is greater than size user passed then simply return the program with the error message “Elements are more than the size specified”.
classArray(object):def__init__(self,size,defaultValue=None): self.size = sizeif(defaultValue ==None): self.items =list()for i inrange(size): self.items.append(defaultValue)else: self.items =list()if(len(defaultValue)== size orlen(defaultValue)< size):for j inrange(len(defaultValue)):if(defaultValue[j]): self.items.append(defaultValue[j])for i inrange(len(defaultValue), size): self.items.append(None)else:print('Elements are more than the size specified')
Define Length of Array Function
This function is used to return the length of the Array that means the elements we initialized excluding None values from it.
def myLen(self):
length = 0
for i in self.items:
if i == None:
continue
else:
length += 1
return length
Define Insert First Array Function
This function is used to insert or add the element to the beginning of the array.
def insertFirst(self, element):
if (self.myLen() < self.size):
for i in range(self.myLen(), 0, -1):
self.items[i] = self.items[i - 1]
self.items[0] = element
else:
print('Element index out of range')
Define Insert At Index Function
This function is used to insert or add an element at a particular index or position which the user passed along with the element to insert.
def insertAtIndex(self, index, element):
if (self.myLen() < self.size):
for i in range(self.myLen(), index, -1):
self.items[i] = self.items[i - 1]
self.items[index] = element
else:
print('Element index out of range')
Define Insert After Index Function
This function is used to insert or add an element after a particular index or position which the user passed along with the element to insert.
def insertAfterIndex(self, index, element):
if (self.myLen() < self.size):
for i in range(self.myLen(), index + 1, -1):
self.items[i] = self.items[i - 1]
self.items[index + 1] = element
else:
print('Element index out of range')
Define Insert Before Index Function
This function is used to insert or add an element before a particular index or position which the user passed along with the element to insert.
def insertBeforeIndex(self, index, element):
if (self.myLen() < self.size):
for i in range(self.myLen(), index - 1, -1):
self.items[i] = self.items[i - 1]
self.items[index - 1] = element
else:
print('Element index out of range')
Define Delete Function
This function is used to remove or delete a particular element from our array or if not present then simply print the error that the element is not found in this array.
def delete(self, element):
if element in self.items:
Index = self.items.index(element)
self.items[Index] = None
else:
print('This element is not in the Array!')
Define Search Function
This function is used to search or find the element which is passed by the user to return the index or position.
def search(self, element):
if element in self.items:
position = 0
for i in range(self.myLen()):
if(self.items[i] == element):
break
else:
position += 1
print('Element {} found at position {}'.format(element, position))
else:
print('This element is not in the Array!')
Define Main Condition
Now, we have implemented all the functions of our custom Array class.
So, now what we need is to check whether the functionality of these methods are working or not.
For that, create an instance of the Array Class and initialize it with array size and the values it needs to insert at the beginning.
Then, just use the object to call all the functions one by one.