Many times we require to find the first occurring non-zero number to begin the processing with. This has mostly use case in Machine Learning domain in which we require to process data excluding None or 0 values. Let’s discuss certain ways in which this can be performed.
Method #1 : Using next() + enumerate() The next function can be used to iterate through the list and enumerate along with it checks for the list if the number is a non zero element and returns the number of 0s before a True value i.e a non zero value.
Python3
# Python3 code to demonstrate# finding first True value# using next() and enumerate()# initializing listtest_list = [0, 0, 5, 6, 0]# printing original listprint("The original list is : " + str(test_list))# finding first True value# using next() and enumerate()res = next((i for i, j in enumerate(test_list) if j), None)# printing resultprint("The values till first True value : " + str(res)) |
The original list is : [0, 0, 5, 6, 0] The values till first True value : 2
Time complexity: O(n) where n is the length of the list ‘test_list’. This is because the program uses a for loop to go through each element in the list and check if the element is True.
Auxiliary space: O(1) as the program only uses a single variable ‘res’ to store the result.
Method #2 : Using filter() + lambda + index() Using the combination of the above functions, one can easily perform this particular task. The filter function can be used to screen out the True value that is processed by the lambda functions and index function returns the first occurrence of this.
Python3
# Python3 code to demonstrate# finding first True value# using filter() + lambda + index()# initializing listtest_list = [0, 0, 5, 6, 0]# printing original listprint("The original list is : " + str(test_list))# finding first True value# using filter() + lambda + index()res = test_list.index(next(filter(lambda i: i != 0, test_list)))# printing resultprint("The values till first True value : " + str(res)) |
The original list is : [0, 0, 5, 6, 0] The values till first True value : 2
Time complexity: O(n)
Auxiliary space: O(1)
Method #3 : Using for loop
Python3
# Python3 code to demonstrate# finding first True value# initializing listtest_list = [0, 0, 5, 6, 0]# printing original listprint("The original list is : " + str(test_list))# finding first True valuec = 0for i in range(0, len(test_list)): if(test_list[i] == 0): c += 1 else: break# printing resultprint("The values till first True value : " + str(c)) |
The original list is : [0, 0, 5, 6, 0] The values till first True value : 2
Time complexity: O(n)
Auxiliary space: O(n), where n is length of list.
Method #4 : Using min()+enumerate()
The approach is to use list comprehension to create a new list containing only the non-zero elements of the original list, and then use the min() function to find the index of the first non-zero element. This approach involves creating a new list with a list comprehension that filters out the zero elements, and then using the min() function with the key argument set to the list.index function to find the index of the first element in the new list. This approach has a time complexity of O(n) and a space complexity of O(n), as the list comprehension iterates over the entire list and creates a new list of the same size.
Here is an example of how this approach could be implemented in Python:
Python3
# Python3 code to find the first occurrence of a non-zero element# Initialize the listtest_list = [0, 0, 5, 6, 0]# Print the original listprint("The original list is:", test_list)# Find the index of the first non-zero elementnon_zero_indices = [i for i, x in enumerate(test_list) if x]first_non_zero_index = min(non_zero_indices, default=None)# Print the resultprint("The first occurrence of a non-zero element is at index:", first_non_zero_index)#This code is contributed by Edula Vinay Kumar Reddy |
The original list is: [0, 0, 5, 6, 0] The first occurrence of a non-zero element is at index: 2
Time Complexity: O(n), where n is the length of the list test_list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list
Method#5: Using recursion
Python3
# Python3 code to demonstrate# finding first True value# using recursiondef check(l,i): if i == len(l): return -1 if l[i]: return i return check(l,i+1)# initializing listtest_list = [0, 0, 5, 6, 0]# printing original listprint("The original list is : " + str(test_list))res = check(test_list,0)# Print the resultprint("The first occurrence of a non-zero element is at index:",res)#This code is contributed by Vinay Pinjala. |
The original list is : [0, 0, 5, 6, 0] The first occurrence of a non-zero element is at index: 2
Time complexity: O(n)
Auxiliary Space: O(n)
Method#6: Using List comprehension.
Python3
# Python3 code to demonstrate# finding first True value# using list comprehensiondef first_non_zero(l): non_zero = [i for i, item in enumerate(l) if item] return non_zero[0] if non_zero else -1# initializing listtest_list = [0, 0, 5, 6, 0]# printing original listprint("The original list is : " + str(test_list))res = first_non_zero(test_list)# Print the resultprint("The first occurrence of a non-zero element is at index:",res)#This code is contributed by tvsk. |
The original list is : [0, 0, 5, 6, 0] The first occurrence of a non-zero element is at index: 2
Time Complexity: O(n)
Auxiliary Space: O(n)
Method#7: Using reduce method:
This code aims to find the index of the first non-zero element in a list of integers. It does so by using the reduce() function from the functools module in Python. The reduce() function is used to iteratively apply a function to a list, in order to reduce it to a single value.
In this code, the reduce() function is used with a lambda function that takes an accumulator value (acc) and an index (i) as input. The lambda function checks if the current element in the list is non-zero, and if it is, it returns the index of that element. If the element is zero, it returns None. The reduce() function then applies the lambda function to the list of indices (range(len(test_list))) and returns the index of the first non-zero element it encounters, or None if there are no non-zero elements.
The result is then printed to the console, indicating the index of the first non-zero element in the original list.
Python3
# import reduce function from functools modulefrom functools import reduce# initializing listtest_list = [0, 0, 5, 6, 0]# print original listprint("The original list is : " + str(test_list))# using reduce() function to find first True value# initialize accumulator (acc) to None and use a lambda function to determine the next valueres = reduce(lambda acc, i: acc if acc is not None else i if test_list[i] else None, range(len(test_list)), None)# printing resultprint("The first occurrence of a non-zero element is at index:" + str(res))#This code is contributed by Jyothi pinjala |
The original list is : [0, 0, 5, 6, 0] The first occurrence of a non-zero element is at index:2
Time Complexity: O(n)
Auxiliary Space: O(1)
Method #8: Using numpy
Step-by-step approach:
- Import numpy library
- Convert the given list to numpy array using np.array()
- Use np.where() function to find the index of the first non-zero element in the array
- If the index is found, return the index, else return None
Below is the implementation of the above approach:
Python3
# Python3 code to demonstrate# finding first True value# using numpy# importing numpy libraryimport numpy as np# initializing listtest_list = [0, 0, 5, 6, 0]# printing original listprint("The original list is : " + str(test_list))# finding first True value# using numpyres = np.where(np.array(test_list) != 0)[0]if res.size: res = res[0]else: res = None# printing resultprint("The values till first True value : " + str(res)) |
Output:
The original list is : [0, 0, 5, 6, 0] The values till first True value : 2
Time complexity: O(n)
Auxiliary space: O(n)
Method #9: Using itertools module:
Algorithm:
- Import the dropwhile function from the itertools module.
- Define the input list test_list.
- Print the original list.
- Use dropwhile to drop all the elements from the beginning of the list until the first non-zero element is found,
- and then return the remaining elements. Store the index of the first non-zero element in the index variable using the next function.
- Subtract 3 from the index to get the index of the third element before the first non-zero element.
Slice the input list up to the index-3 to get the values till the first non-zero element and store it in values_till_first_true variable. - Print the values till the first non-zero element and their count.
Python3
from itertools import dropwhiletest_list = [0, 0, 5, 6, 0]print("The original list is : " + str(test_list))index = next(dropwhile(lambda x: x == 0, test_list))values_till_first_true = test_list[:index-3]values_count = len(values_till_first_true)print("The number of values till first True value : ", values_count)#This code is contributed by Rayudu |
The original list is : [0, 0, 5, 6, 0] The number of values till first True value : 2
Time Complexity:
The time complexity of this code is O(n) because we need to iterate through the entire list once to find the index of the first non-zero element, and then slice the list up to that index.
Auxiliary Space:
The space complexity of this code is also O(n) because we are storing the entire input list in the test_list variable, and then creating two additional variables index and values_till_first_true to store the index of the first non-zero element and the values till the first non-zero element respectively.
Method #10: Using heapq:
- Create a list of tuples where each tuple contains an element from the input list and its corresponding index. This can be done using a list comprehension and the enumerate() function.
- Use heapq.heapify() to convert the list of tuples into a heap data structure, where each tuple is ordered by its first element (the value from the input list).
- Use a while loop to pop the smallest tuple from the heap until a tuple with a non-zero value is found. This is done using heapq.heappop(), which removes and returns the smallest item from the heap.
- If a non-zero tuple is found, return its index. If the heap becomes empty (i.e., all values in the input list are zero), return None.
Python3
import heapqdef find_first_nonzero_index(lst): heap = [(val, idx) for idx, val in enumerate(lst)] heapq.heapify(heap) while heap: val, idx = heapq.heappop(heap) if val != 0: return idx return None# Example usage:test_list = [0, 0, 5, 6, 0]# printing original listprint("The original list is : " + str(test_list))first_nonzero_index = find_first_nonzero_index(test_list)print("The index of the first non-zero element is:", first_nonzero_index)#This code is contributed by Vinay Pinjala. |
The original list is : [0, 0, 5, 6, 0] The index of the first non-zero element is: 2
The time complexity :O(n log n), where n is the length of the input list. This is due to the use of heapq.heapify() to create the heap, which has a time complexity of O(n log n). The while loop then takes O(n) time in the worst case, as it must pop every element from the heap.
The space complexity :O(n), as the heap requires additional memory to store the tuples.
