Given a list of numbers and a particular element from the list, the task is to write a Python program to get the next unrevealed element to the first occurrence of a given element i.e element that does not occur till the given element.
Examples:
Input : test_list = [3, 4, 6, 6, 3, 2, 3, 5, 6, 3, 4, 5, 5, 3, 6], nex_to_ele = 6
Output : 2
Explanation : In the above list there are 2, 3, 4, 5, and 6 are elements, as nex_to_ele is 6, whose first occurrence is at index 2, before that only 3 and 4 occurs, so the unrevealed elements are 2 and 5, out of which unrevealed element 2 is next after the first occurrence of 6. Hence 2 is the next unrevealed element of 6 in the list.
Input : test_list = [3, 4, 6, 6, 3, 2, 3, 5, 6, 3, 4, 5, 5, 3, 6], nex_to_ele = 3
Output : 4
Explanation : Next different unrevealed element to 3 is 4 as 3 occurs at index 0. So, none of the elements in the list have occurred before 3 and 4 is the next element after 3.
Method #1 : Using set() + sorted() + index()
In this, the list is converted to a unique element list preserving order using set() and sorted(). Then index() is used to get the index of number and the next element to it in the result list is the required element.
Python3
# Python3 code to demonstrate working of# Next different element in list# Using set() + sorted() + index()# initializing listtest_list = [3, 4, 6, 6, 3, 2, 3, 5, 6, 3, 4, 5, 5, 3, 6]# printing original listprint("The original list is : " + str(test_list))# initializing elementnex_to_ele = 6# sorting removing duplicated keeping ordertemp = sorted(set(test_list), key=lambda sub: test_list.index(sub))# getting next indexnum_idx = temp.index(nex_to_ele)# checking for last index for overflowif num_idx == len(temp) - 1: res = None# getting next index as resultelse: res = temp[num_idx + 1]# printing resultprint("Next different element : " + str(res)) |
Output:
The original list is : [3, 4, 6, 6, 3, 2, 3, 5, 6, 3, 4, 5, 5, 3, 6]
Next different element : 2
Time Complexity: O(nlogn)
Auxiliary Space: O(n)
Method #2 : Using next() + iter() + sorted() + set()
In this, we don’t use index() to get element index, rather user iterator approach to increment to next the iterator till the element is found. The next element to it is result.
Python3
# Python3 code to demonstrate working of# Next different element in list# Using next() + iter() + sorted() + set()# initializing listtest_list = [3, 4, 6, 6, 3, 2, 3, 5, 6, 3, 4, 5, 5, 3, 6]# printing original listprint("The original list is : " + str(test_list))# initializing elementnex_to_ele = 6# sorting removing duplicated keeping ordertemp = sorted(set(test_list), key=lambda sub: test_list.index(sub))temp_itr = iter(temp)flag = 0for idx in range(0, len(temp)): # if last element is element to find if idx == len(temp) - 1: flag = 1 # breaking when element is found if next(temp_itr) == nex_to_ele: breakif flag: res = Noneelse: # next element is answer res = next(temp_itr)# printing resultprint("Next different element : " + str(res)) |
Output:
The original list is : [3, 4, 6, 6, 3, 2, 3, 5, 6, 3, 4, 5, 5, 3, 6]
Next different element : 2
Time Complexity: O(nlogn+mlogm)
Auxiliary Space: O(k)
Method #3 : Using Dictionary
Python3
# Python3 code to demonstrate working of# Next different element in listfreq = {}# initializing listtest_list = [3, 4, 6, 6, 3, 2, 3, 5, 6, 3, 4, 5, 5, 3, 6]# printing original listprint("The original list is : " + str(test_list))# initializing elementnex_to_ele = 6for i in range(len(test_list)): if test_list[i] in freq.keys(): freq[test_list[i]] = freq[test_list[i]]+1 else: freq[test_list[i]] = 1 if test_list[i] == nex_to_ele: index = i breakfor i in range(index+1, len(test_list)): if test_list[i] not in freq.keys(): res = test_list[i] break# printing resultprint("Next different element : " + str(res)) |
The original list is : [3, 4, 6, 6, 3, 2, 3, 5, 6, 3, 4, 5, 5, 3, 6] Next different element : 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Method #4: Using numpy:
Algorithm:
1.Initialize an empty dictionary ‘freq’ to store the frequency of elements.
2.Iterate through the list ‘test_list’ and update the frequency of each element in the ‘freq’ dictionary.
3.Find the index of the given element ‘nex_to_ele’ in ‘test_list’.
4.Iterate through the list ‘test_list’ from index ‘index+1’ to the end and check if an element is not present in the ‘freq’ dictionary. The first such element encountered is the next different element.
5.If no such element is found, there is no next different element.
6.Print the next different element if found, else print a message indicating that there is no next different element.
Python3
import numpy as np# initializing listtest_list = [3, 4, 6, 6, 3, 2, 3, 5, 6, 3, 4, 5, 5, 3, 6]# printing original listprint("The original list is : " + str(test_list))# initializing elementnex_to_ele = 6# creating numpy array from listarr = np.array(test_list)# finding index of the given elementindex = np.where(arr == nex_to_ele)[0][0]# finding the next different element using numpy's unique() and sort() functionsnext_diff = np.unique(arr[index+1:])next_diff = next_diff[next_diff != nex_to_ele]next_diff = np.sort(next_diff)# printing resultif next_diff.size > 0: print("Next different element : " + str(next_diff[0]))else: print("There is no next different element.")#This code is contributed by Jyothi pinjala |
Output:
The original list is : [3, 4, 6, 6, 3, 2, 3, 5, 6, 3, 4, 5, 5, 3, 6]
Next different element : 2
Time Complexity: O(n) where ‘n’ is the length of the input list. This is because we are iterating through the list twice, once to update the frequency of elements and once to find the next different element. The time taken for updating the frequency of elements in the dictionary is O(n) and the time taken to find the next different element is also O(n). The overall time complexity is O(n) + O(n) = O(n).
Auxiliary Space: O(k) where ‘k’ is the number of unique elements in the input list. This is because we are using a dictionary to store the frequency of elements, and the size of the dictionary is proportional to the number of unique elements in the list. The worst case scenario is when all elements in the list are unique, in which case the space complexity is O(n).
