Given an array a[] of size N which contains elements from 0 to N-1, you need to find all the elements occurring more than once in the given array.
Complete the function duplicates() which takes array a[] and n as input as parameters and returns a list of elements that occur more than once in the given array in sorted manner. If no such element is found, return list containing [-1].
Note : The extra space is only for the array to be returned. Try and perform all operation withing the provided array.
1 <= N <= 105
0 <= A[i] <= N-1, for each valid i
Input:
N = 4
a[] = {0,3,1,2}
Output: -1
Explanation: N=4 and all elements from 0
to (N-1 = 3) are present in the given
array. Therefore output is -1.Input:
N = 5
a[] = {2,3,1,2,3}
Output: 2 3
Explanation: 2 and 3 occur more than once
in the given array.class Solution:
def duplicates(self, arr, n):
# code here
flags = False
array_dict = {}
repeating_arr = []
# loop through array and add to dictionary with the number of times it repeats
for a in arr:
if a not in array_dict:
array_dict[a] = 1
else:
array_dict[a] += 1
# loop dictionary and append all repeating values to repeating array
for j in array_dict:
if array_dict[j] > 1:
flags = True
repeating_arr.append(j)
repeating_arr.sort()
# if there is a flag for repeating character return [-1] or return sorted array
if not flags: return [-1]
return repeating_arr- We first loop through the array and add values to an empty dictionary. If the value does not exist, we add it to the dictionary with a value of 1. If it exists, we increment the existing value in the dictionary by 1 and set our flag value to True (Meaning there are repeating characters. We will use this value to determine our return result)
- We now loop through the dictionary. Every key we find with a value greater than 1 means they repeat. We append that key to our empty repeating array.
- If flags is false we return -1. If not, we apply the sort method to our array and return our array.
Photo by Pakata Goh on Unsplash
