Python – Test for Incrementing Dictionary

0 0 4 minutes read

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 dictionary
test_dict = {1: 2, 3: 4, 5: 6, 7: 8}
 
# printing original dictionary
print("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 elements
res = True
for idx in range(0, len(temp) - 1):
 
    # test for increasing list
    if temp[idx + 1] - 1 != temp[idx]:
        res = False
 
# printing result
print("Is dictionary incrementing : " + str(res))

Output

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 dictionary
test_dict = {1: 2, 3: 10, 5: 6, 7: 8}
 
# printing original dictionary
print("The original dictionary is : " + str(test_dict))
 
res = False
 
x = 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 result
print("Is dictionary incrementing : " + str(res))

Output

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 dictionary
test_dict = {1: 2, 3: 10, 5: 6, 7: 8}
 
# printing original dictionary
print("The original dictionary is : " + str(test_dict))
res = False
x = 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 result
print("Is dictionary incrementing : " + str(res))

Output

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 dictionary
test_dict = {1: 2, 3: 9, 5: 6, 7: 8}
# printing original dictionary
print("The original dictionary is : " + str(test_dict))
# Call the function and pass in the test dictionary as an argument
print("Is dictionary incrementing:", is_incrementing(test_dict))
# This code is contributed by Jyothi pinjala

Output

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 dictionary
print("The original dictionary is : " + str(test_dict))
print(is_incrementing(test_dict)) 
#This code is contributed by Rayudu.

Output

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 dictionary
print("The original dictionary is : " + str(test_dict))
print(is_incrementing(test_dict))

Output

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