Sometimes, we might have a problem in which we require to get the maximum difference of 2 numbers from list but with a constraint of having the numbers in successions. This type of problem can occur while competitive programming. Let’s discuss certain ways in which this problem can be solved.
Method #1 : Using max() + zip() + list comprehension This problem can be solved using the combination of above three function in which max function can be used to get the maximum value, zip and list comprehension doing the task of extending the logic to the whole list.
Python3
# Python3 code to demonstrate # Consecutive Character Maximum difference # using zip() + max() + list comprehension # initializing string test_string = '6543452345456987653234' # printing original string print ( "The original string : " + str (test_string)) # using zip() + max() + list comprehension # Consecutive Character Maximum difference test_string = list (test_string) res = max ( abs ( int (a) - int (b)) for a, b in zip (test_string, test_string[ 1 :])) # print result print ( "The maximum consecutive difference is : " + str (res)) |
The original string : 6543452345456987653234 The maximum consecutive difference is : 3
Method #2 : Using max() + map() + operator.sub The above problem can also be solved using yet another combination of functions. In this combination, map functions performs the task of extending the logic to whole list and mul operator is used to perform the difference.
Python3
# Python3 code to demonstrate # Consecutive Character Maximum difference # using max() + map() + operator.sub from operator import sub # initializing string test_string = '6543452345456987653234' # printing original string print ( "The original string : " + str (test_string)) # using max() + map() + operator.sub # Consecutive Character Maximum difference res = max ( map (sub, map ( int , test_string), map ( int , test_string[ 1 :]))) # print result print ( "The maximum consecutive difference is : " + str (res)) |
The original string : 6543452345456987653234 The maximum consecutive difference is : 3
The Time and Space Complexity for all the methods are the same:
Time Complexity: O(nlogn)
Auxiliary Space: O(n)
Method #3 : Using reduce()
Here’s an implementation using reduce from the functools module:
Python3
from functools import reduce def consecutive_max_difference(test_string): # Convert test_string to list of integers test_string = list ( map ( int , test_string)) # Use reduce to find maximum difference return reduce ( lambda x, y: max (x, abs (y[ 0 ] - y[ 1 ])), zip (test_string, test_string[ 1 :]), 0 ) # Test test_string = '6543452345456987653234' print ( "The maximum consecutive difference is :" , consecutive_max_difference(test_string)) #This code is contributed by Edula Vinay Kumar Reddy |
The maximum consecutive difference is : 3
This code has the same time and space complexity as the previous methods, which is O(n) time complexity and O(n) auxiliary space.
Method #4 : Using itertools.groupby:
Python3
import itertools def max_consecutive_difference(s): s = list ( map ( int , s)) groups = [ list (g) for k, g in itertools.groupby(s)] max_diff = 0 for i in range ( len (groups) - 1 ): diff = abs (groups[i][ 0 ] - groups[i + 1 ][ 0 ]) if diff > max_diff: max_diff = diff return max_diff test_string = '6543452345456987653234' # printing original string print ( "The original string : " + str (test_string)) print ( "The maximum consecutive difference is:" , max_consecutive_difference(test_string)) #This code is contributed by Jyothi pinjala. |
The original string : 6543452345456987653234 The maximum consecutive difference is: 3
Time complexity: O(n)
Auxiliary space: O(n)
Method 5 : using an iterative approach”.
- Initialize the string to be checked.
- Print the original string.
- Initialize a variable max_diff to 0 to keep track of the maximum consecutive difference.
- Use a loop to iterate over the characters in the string.
- In each iteration, calculate the absolute difference between the current character and the next character.
- If the difference is greater than the current maximum difference, update the max_diff variable.
- After the loop ends, print the maximum consecutive difference found in the string.
Python3
# Python3 code to demonstrate # Consecutive Character Maximum difference # using iterative approach # initializing string test_string = '6543452345456987653234' # printing original string print ( "The original string : " + str (test_string)) max_diff = 0 for i in range ( len (test_string) - 1 ): diff = abs ( int (test_string[i]) - int (test_string[i + 1 ])) if diff > max_diff: max_diff = diff # print result print ( "The maximum consecutive difference is : " + str (max_diff)) |
The original string : 6543452345456987653234 The maximum consecutive difference is : 3
The time complexity of this approach is O(n), where n is the length of the string.
The space complexity is O(1), as we are only storing a few variables to keep track of the maximum difference seen so far.
Method #6 : Using numpy :
Algorithm:
- Convert the input string into a numpy array of integers.
- Split the array into groups whenever there is a gap of more than 1 between consecutive elements.
- Iterate through each group and calculate the difference between the first and last element of the group.
- Update the maximum difference if the current difference is greater than the current maximum difference.
- Return the maximum difference.
Python3
import numpy as np import itertools def max_consecutive_difference(s): s = np.array( list ( map ( int , s))) groups = np.split(s, np.where(np.diff(s) ! = 1 )[ 0 ] + 1 ) max_diff = 0 for group in groups: if len (group) > 1 : diff = np. abs (group[ - 1 ] - group[ 0 ]) if diff > max_diff: max_diff = diff return max_diff # Example input test_string = '6543452345456987653234' # Call the function and print the output print ( "The original string : " + str (test_string)) print ( "The maximum consecutive difference is:" , max_consecutive_difference(test_string)) #This code is contributed by Rayudu. |
Output: The original string : 6543452345456987653234 The maximum consecutive difference is: 3
Time Complexity:
The time complexity is O(n), where n is the length of the input string. This is because the algorithm iterates through the string only once to split it into groups and calculate the maximum difference.
Auxiliary Space:
The space complexity is O(n), where n is the length of the input string. This is because the input string is converted into a numpy array of integers, which takes O(n) space. Additionally, the algorithm uses numpy arrays to store the groups of consecutive integers, which also takes O(n) space. Overall, the space complexity of this algorithm is linear in the size of the input.