Given a dictionary, test if it is incrementing, i.e. its key and values are increasing by 1.
Input : test_dict = {1:2, 3:4, 5:6, 7:8}
Output : True
Explanation : All keys and values in order differ by 1.Input : test_dict = {1:2, 3:10, 5:6, 7:8}
Output : False
Explanation : Irregular items.
Method 1: Using items() + loop + extend() + list comprehension
In this, 1st step is to get the dictionary to list conversion using items() + list comprehension and extend(), next loop is used to test if the converted list is incremental.
Python3
# Python3 code to demonstrate working of# Test for Incrementing Dictionary# Using extend() + list comprehension# initializing dictionarytest_dict = {1: 2, 3: 4, 5: 6, 7: 8}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))temp = []# forming list from dictionary[temp.extend([key, val]) for key, val in test_dict.items()]# checking for incrementing elementsres = Truefor idx in range(0, len(temp) - 1): # test for increasing list if temp[idx + 1] - 1 != temp[idx]: res = False# printing resultprint("Is dictionary incrementing : " + str(res)) |
The original dictionary is : {1: 2, 3: 4, 5: 6, 7: 8}
Is dictionary incrementing : True
Time complexity: O(n), where n is the number of items in the dictionary. The time complexity is determined by the for loop that iterates through the list formed from the dictionary.
Auxiliary space: O(n), where n is the number of items in the dictionary. The auxiliary space is determined by the use of a list “temp” that stores the key-value pairs from the dictionary.
Method 2: Using keys(),values() and sort() method
Python3
# Python3 code to demonstrate working of# Test for Incrementing Dictionary# initializing dictionarytest_dict = {1: 2, 3: 10, 5: 6, 7: 8}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))res = Falsex = list(test_dict.keys())y = list(test_dict.values())a = []for i in range(0, len(x)): a.append(x[i]) a.append(y[i]) b = []b.extend(a)b.sort()if(a == b): res = True# printing resultprint("Is dictionary incrementing : " + str(res)) |
The original dictionary is : {1: 2, 3: 10, 5: 6, 7: 8}
Is dictionary incrementing : False
Time Complexity: O(n log n)
Auxiliary Space: O(n)
Method 3: Using replace(),list(),map(),extend(),sort() methods
Python3
# Python3 code to demonstrate working of# Test for Incrementing Dictionary# initializing dictionarytest_dict = {1: 2, 3: 10, 5: 6, 7: 8}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))res = Falsex = str(test_dict)x = x.replace("{", "")x = x.replace("}", "")x = x.replace(":", "")x = x.replace(",", "")y = x.split()y = list(map(int, y))a = []a.extend(y)y.sort()if(a == y): res = True# printing resultprint("Is dictionary incrementing : " + str(res)) |
The original dictionary is : {1: 2, 3: 10, 5: 6, 7: 8}
Is dictionary incrementing : False
Time complexity: O(n log n), where n is the number of key-value pairs in the dictionary.
Auxiliary space: O(n), where n is the number of key-value pairs in the dictionary.
Method 4: Using all() and zip()
Python3
def is_incrementing(dictionary): # Use the built-in `all` function to check if all elements in the generator expression are `True` # The generator expression `(val - 1 == prev for prev, val in zip(dictionary.keys(), dictionary.values()))` # generates a sequence of booleans that represent whether the difference between each key and value is 1 # If all elements in the sequence are `True`, `all` returns `True`; otherwise, it returns `False` return all(val - 1 == prev for prev, val in zip(dictionary.keys(), dictionary.values()))# Define the test dictionarytest_dict = {1: 2, 3: 9, 5: 6, 7: 8}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# Call the function and pass in the test dictionary as an argumentprint("Is dictionary incrementing:", is_incrementing(test_dict))# This code is contributed by Jyothi pinjala |
The original dictionary is : {1: 2, 3: 9, 5: 6, 7: 8}
Is dictionary incrementing: False
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 5: Using recursion:
- Convert the dictionary keys and values to lists.
- If the length of the keys list is 1, return True (a single key-value pair is always considered incrementing).
- Otherwise, check if the difference between the first value and the first key is 1. If so, recursively call the function with a new dictionary created by zipping the remaining keys and values lists together.
- If the difference is not 1 or if the recursion reaches a single key-value pair that is not incrementing, return False.
Python3
def is_incrementing(dictionary): keys = list(dictionary.keys()) values = list(dictionary.values()) if len(keys) == 1: return True elif values[0] - keys[0] == 1: return is_incrementing(dict(zip(keys[1:], values[1:]))) else: return False# Example usage:test_dict = {1: 2, 2: 3, 3: 4, 4: 5}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))print(is_incrementing(test_dict)) #This code is contributed by Rayudu. |
The original dictionary is : {1: 2, 2: 3, 3: 4, 4: 5}
True
Time complexity: O(n) where n is the number of key-value pairs in the dictionary. This is because the function must iterate over each key-value pair in the dictionary once.
Auxiliary space: O(n) because the function creates two lists of length n (the keys and values lists). However, the recursion depth is at most n-1, so the maximum amount of space used by the call stack is also O(n).
Method 6: Using iteration and a flag variable
- Initialize a flag variable “is_incremental” to True.
- Iterate over the dictionary using a for loop and Check if the current key is equal to the previous key + 1, if not set the flag variable “is_incremental” to False and break the loop.
- Return the flag variable “is_incremental”
Python3
def is_incrementing(dictionary): keys = list(dictionary.keys()) is_incremental = True for i in range(1, len(keys)): if keys[i] != keys[i-1] + 1 or dictionary[keys[i]] != dictionary[keys[i-1]] + 1: is_incremental = False break return is_incremental# Example usage:test_dict = {1: 2, 2: 3, 3: 4, 4: 5}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))print(is_incrementing(test_dict)) |
The original dictionary is : {1: 2, 2: 3, 3: 4, 4: 5}
True
Time Complexity: O(n), where n is the number of key-value pairs in the dictionary
Auxiliary Space: O(1), as we are not using any additional data structure
