Given an array arr[] of length n and an integer k, the task is to find the length of the maximum distinct subarray formed after adding k or subtracting k or none.
Examples:
Input: arr = [1, 2, 3, 4, 5], k = 1
Output: 5
Explanation: In this test case, the array has 5 distinct elements, and k is 1. The subarray with the maximum number of distinct elements is the entire array, so the function should return 5.Input: arr = [1, 2, 3, 3, 4, 5], k = 0
Output: 3
Explanation: In this test case, the array has 5 distinct elements, and k is 0. The subarray with the maximum number of distinct elements is [1, 2, 3] and [3, 4, 5], so the function should return 3.
Approach: The above problem can be solved with the below:
The approach used in the algorithm is to iterate through the elements in the array and maintain a set of distinct elements in the current subarray. At each step, the algorithm checks if the current element x or x – k or x + k is in the set.
- If x is not in the set, it is added to the set.
- If x – k is in the set, it is removed and x is added to the set.
- If x + k is in the set, it is removed and x is added to the set.
In this way, the set always contains the distinct elements in the current subarray, and the size of the set is equal to the length of the current distinct subarray. The maximum length of the distinct subarray is updated whenever the size of the set is larger than the current maximum length.
This approach works because the addition or subtraction of k to or from an element does not change the distinctness of the element. If an element is distinct, adding or subtracting k to or from it will still make it distinct. Similarly, if an element is not distinct, adding or subtracting k to or from it will still make it not distinct. Therefore, adding or subtracting k to or from an element does not effect the distinctness of the elements in the current subarray.
Follow the given steps to solve the problem:
- Initialize a variable max_length to 0. This variable will keep track of the maximum length of the distinct subarray found so far.
- Initialize a set of distinct_elements to an empty set. This set will store the distinct elements in the current subarray.
- Iterate through the elements in the array. For each element x, do the following:
- If x – k or x + k is not in the set distinct_elements, add x to the set.
- If x – k or x + k is in the set distinct_elements, remove x – k or x + k from the set and add x to the set.
- Update the variable max_length to the maximum of max_length and the size of the set distinct_elements.
- Return max_length.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find distinct subarrayint max_distinct_subarray(int arr[], int n, int k) { int max_length = 0; set<int> distinct_elements; for (int i = 0; i < n; i++) { // If arr[i] - k and arr[i] + k is present if (distinct_elements.find(arr[i] - k) == distinct_elements.end() && distinct_elements.find(arr[i] + k) == distinct_elements.end()) { distinct_elements.insert(arr[i]); } // If arr[i] - k is present and add arr[i] else if (distinct_elements.find(arr[i] - k) != distinct_elements.end()) { distinct_elements.erase(arr[i] - k); distinct_elements.insert(arr[i]); } // If arr[i] + k is present and add arr[i] else if (distinct_elements.find(arr[i] + k) != distinct_elements.end()) { distinct_elements.erase(arr[i] + k); distinct_elements.insert(arr[i]); } // Update the maximum length max_length = max(max_length, (int)distinct_elements.size()); } return max_length;}// Drive Codeint main() { // Input int arr[] = {1, 2, 3, 4, 5}; int k = 0; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << max_distinct_subarray(arr, n, k) << "\n" ; return 0;}// This code is contributed by nikhilsainiofficial546 |
Java
// Java implementation of the above approachimport java.io.*;import java.util.*;class GFG { static int maxDistinctSubarray(int[] arr, int n, int k) { int maxLength = 0; Set<Integer> distinctElements = new HashSet<>(); for (int i = 0; i < n; i++) { // If arr[i] - k and arr[i] + k is not present if (!distinctElements.contains(arr[i] - k) && !distinctElements.contains(arr[i] + k)) { distinctElements.add(arr[i]); } // If arr[i] - k is present and add arr[i] else if (distinctElements.contains(arr[i] - k)) { distinctElements.remove(arr[i] - k); distinctElements.add(arr[i]); } // If arr[i] + k is present and add arr[i] else if (distinctElements.contains(arr[i] + k)) { distinctElements.remove(arr[i] + k); distinctElements.add(arr[i]); } // Update the maximum length maxLength = Math.max(maxLength, distinctElements.size()); } return maxLength; } public static void main(String[] args) { // Input int[] arr = { 1, 2, 3, 4, 5 }; int k = 0; int n = arr.length; // Function call System.out.println(maxDistinctSubarray(arr, n, k)); }}// This code is contributed by lokesh. |
Python3
# Python implementation of the above approach# Function to find distinct subarraydef max_distinct_subarray(arr, k): max_length = 0 distinct_elements = set() for x in arr: # If x - k and x + k is present if x - k not in distinct_elements and x + k not in distinct_elements: distinct_elements.add(x) # If x - k is present and add x elif x - k in distinct_elements: distinct_elements.remove(x - k) distinct_elements.add(x) # If x + k is present and add x elif x + k in distinct_elements: distinct_elements.remove(x + k) distinct_elements.add(x) # Update the maximum length max_length = max(max_length, len(distinct_elements)) return max_length# Driver code# Inputarr = [1, 2, 3, 4, 5]k = 0# Function callprint(max_distinct_subarray(arr, k)) |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;public class GFG { static int maxDistinctSubarray(int[] arr, int n, int k) { int maxLength = 0; HashSet<int> distinctElements = new HashSet<int>(); for (int i = 0; i < n; i++) { // If arr[i] - k and arr[i] + k is not present if (!distinctElements.Contains(arr[i] - k) && !distinctElements.Contains(arr[i] + k)) { distinctElements.Add(arr[i]); } // If arr[i] - k is present and add arr[i] else if (distinctElements.Contains(arr[i] - k)) { distinctElements.Remove(arr[i] - k); distinctElements.Add(arr[i]); } // If arr[i] + k is present and add arr[i] else if (distinctElements.Contains(arr[i] + k)) { distinctElements.Remove(arr[i] + k); distinctElements.Add(arr[i]); } // Update the maximum length maxLength = Math.Max(maxLength, distinctElements.Count); } return maxLength; } static public void Main() { // Input int[] arr = { 1, 2, 3, 4, 5 }; int k = 0; int n = arr.Length; // Function call Console.WriteLine(maxDistinctSubarray(arr, n, k)); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript implementation of the above approach// Function to find distinct subarrayfunction max_distinct_subarray(arr, n, k) { let max_length = 0; let distinct_elements=new Set(); for (let i = 0; i < n; i++) { // If arr[i] - k and arr[i] + k is present if (!distinct_elements.has(arr[i] - k) && !distinct_elements.has(arr[i] + k)) { distinct_elements.add(arr[i]); } // If arr[i] - k is present and add arr[i] else if (distinct_elements.has(arr[i] - k)) { distinct_elements.delete(arr[i] - k); distinct_elements.add(arr[i]); } // If arr[i] + k is present and add arr[i] else if (distinct_elements.has(arr[i] + k)) { distinct_elements.delete(arr[i] + k); distinct_elements.add(arr[i]); } // Update the maximum length max_length = Math.max(max_length, distinct_elements.size); } return max_length;}// Drive Code// Inputlet arr = [1, 2, 3, 4, 5];let k = 0;let n = arr.length;// Function callconsole.log(max_distinct_subarray(arr, n, k)) ;// This code is contributed by poojaagarwal2. |
5
Time complexity: O(n)
Auxiliary space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
