Python Program to get indices of sign change in a list

Given List, the task is to write a python program that extracts all the indices from which sign shift occurred.

Input : test_list = [7, 6, -3, -4, -7, 8, 3, -6, 7, 8]
Output : [1, 4, 6, 7]
Explanation : 6 -> -3, at 1st index, -7 -> 8 at 4th index and so on are shifts.

Input : test_list = [7, 6, -3, -4, -7, 8, 3, 6, 7, 8]
Output : [1, 4]
Explanation : 6 -> -3, at 1st index, -7 -> 8 at 4th index are shifts.

Method 1 : Using loop and conditional statements

In this, we check current and next element to be of opposite signs using conditional statements. Loop is used to iterate through all the elements.

Example:

The original list is : [7, 6, -3, -4, -7, 8, 3, -6, 7, 8]
Sign shift indices : [1, 4, 6, 7]

Time Complexity: O(n), The above code iterates through the list once, hence the time complexity is linear, i.e. O(n).
Space Complexity: O(n), The algorithm uses an additional list to store the result, thus consuming linear space which is O(n).

Method 2 : Using list comprehension

Similar to above method, but this provides a one liner alternative using list comprehension.

Example:

The original list is : [7, 6, -3, -4, -7, 8, 3, -6, 7, 8]
Sign shift indices : [1, 4, 6, 7]

Time Complexity: O(n)
Auxiliary Space: O(n)

Method #3: Recursive method.

Step-by-step approach:

1. Define a recursive function sign_shift_indices that takes test_list, idx, and res as arguments.
2. Check if idx is equal to len(test_list) – 1, if true, then return res.
3. Check if the elements at idx and idx+1 in test_list are successive opposites, if true, then append idx to res.
4. Call the sign_shift_indices function recursively with incremented idx and updated res.
5. In the main program, initialize the test_list and print it.
6. Call the sign_shift_indices function with test_list as argument and print the returned result.

The original list is : [7, 6, -3, -4, -7, 8, 3, -6, 7, 8]
Sign shift indices : [1, 4, 6, 7]

The time complexity of the recursive function sign_shift_indices is O(n), where n is the length of test_list, since it is traversing the list recursively.

 The Auxiliary space is also O(n), because of the space used by the recursive call stack and the list res. Overall time complexity is O(n), and auxiliary space complexity is also O(n).

Method #4: using the built-in zip() function 

The zip() function takes two or more iterable objects as input and returns an iterator that aggregates elements from each iterable object.

Step-by-step approach

• Initialize an empty list res to store the indices of sign shifts.
• Use the zip() function to iterate over pairs of adjacent elements in the test_list.
• Use a loop to iterate over the pairs of adjacent elements obtained from zip().
• Check if the signs of the two elements in each pair are opposite (i.e., one is positive and the other is negative).
• If the signs are opposite, append the index of the first element in the pair to res.
• Return the res list containing the indices of sign shift

The original list is : [7, 6, -3, -4, -7, 8, 3, -6, 7, 8]
Sign shift indices : [1, 4, 6, 7]

Time complexity: O(n). 
Auxiliary space: O(k), where k is the number of sign shifts in the list.

Method #5: Using itertools pairwise() and enumerate()

Step-by-step approach:

• Import the itertools library
• Use the pairwise() function to iterate over the list with two adjacent elements at a time.
• Use enumerate() to get the index of each pair.
• Check if the signs of the two elements are different.
• If the signs are different, append the index to a list.
• Return the list of indices.

Output:

The original list is : [7, 6, -3, -4, -7, 8, 3, -6, 7, 8]
Sign shift indices : [1, 4, 6, 7]

Time complexity: O(n)
Auxiliary space: O(k), where k is the number of indices where the sign changes.