Hackerrank | Longest Subarray with Absolute Difference Constraint

Problem Overview

Given an array of integers, our task is to find the longest subarray such that the absolute difference between any two elements is less than or equal to 1.

Example

a=[1,1,2,2,4,4,5,5,5]

There are two subarrays meeting the criterion: [1,1,2,2] and [4,4,5,5,5]. The maximum length subarray has 5 elements.

Function Description

Complete the pickingNumbers function in the editor below.

pickingNumbers has the following parameter(s):

• int a[n]: an array of integers

Returns

• int: the length of the longest subarray that meets the criterion

Solution Approach

Step 1: Frequency Calculation

We initiate an empty dictionary named frequency to keep track of the occurrences of each unique element in the array. A loop iterates through the elements of the array, updating the frequency of each element in the dictionary.

for num in arr:
    frequency[num] = frequency.get(num, 0) + 1

Step 2: Subarray Length Calculation

We initialize a variable max_length to store the maximum subarray length encountered. Another loop traverses the unique elements in the frequency dictionary. For each element, we calculate the potential subarray length by adding the frequency of the current element and the frequency of the next element (if it exists). The max function updates max_length with the maximum value encountered so far.

for num in frequency:
    max_length = max(max_length, frequency.get(num, 0) + frequency.get(num + 1, 0))

Step 3: Result

The final result stored in max_length represents the length of the longest subarray where the absolute difference between any two elements is less than or equal to 1.

Python Code Implementation

Below is the Python code implementing the solution:

def longest_subarray(arr):
    frequency = {}
    max_length = 0

    for num in arr:
        frequency[num] = frequency.get(num, 0) + 1

    for num in frequency:
        max_length = max(max_length, frequency.get(num, 0) + frequency.get(num + 1, 0))

    return max_length

# Example usage:
arr = [4, 6, 5, 3, 3, 1]
result = longest_subarray(arr)
print("Longest subarray length:", result)

Time Complexity:

1. Frequency Calculation:

• Iterating through the array takes O(n) time, where n is the length of the array.
• Updating the frequency dictionary within the loop is a constant-time operation for each element.

1. Subarray Length Calculation:

• Iterating through the unique elements in the frequency dictionary takes O(u) time, where u is the number of unique elements.
• Inside the loop, accessing the frequencies of elements and their adjacent elements is a constant-time operation.

Therefore, the overall time complexity is O(n + u), where n is the length of the array and u is the number of unique elements.

Space Complexity:

1. Frequency Dictionary:

• The space required for the frequency dictionary depends on the number of unique elements in the array.
• In the worst case, if all elements are unique, the space complexity is O(n).
• In the best case, if all elements are the same, the space complexity is O(1).

1. Other Variables:

• The space required for other variables (e.g., max_length) is constant.

Therefore, the overall space complexity is O(n) in the worst case and O(1) in the best case.

Summary:

• Time Complexity: O(n + u)
• Space Complexity: O(n) (worst case), O(1) (best case)

Conclusion

In conclusion, this solution provides an efficient way to find the longest subarray meeting the absolute difference constraint. It leverages dictionary-based frequency tracking to streamline the calculation process. Feel free to utilize and adapt this solution for your array manipulation challenges.