Maximum Number of Distinct Elements After Operations

Maximum Number of Distinct Elements After Operations - Problem

You are given an integer array nums and an integer k.

You are allowed to perform the following operation on each element of the array at most once:

Add an integer in the range [-k, k] to the element.

Return the maximum possible number of distinct elements in nums after performing the operations.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,4], k = 2

› Output: 3

💡 Note: We can adjust: 1→1, 2→3, 4→5, giving us [1,3,5] with 3 distinct elements. All adjustments are within [-2,2] range.

Example 2 — With Duplicates

$ Input: nums = [4,1,2,2], k = 2

› Output: 4

💡 Note: After sorting [1,2,2,4], we can assign: 1→-1, 2→0, 2→1, 4→2, giving us [-1,0,1,2] with 4 distinct elements.

Example 3 — Small Range

$ Input: nums = [5,5,5], k = 1

› Output: 3

💡 Note: We can adjust to [4,5,6] using adjustments [-1,0,+1], all within range [-1,1], giving 3 distinct elements.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹
0 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and adjustment range k

Process

Sort array and greedily assign smallest available values

Output

Maximum possible distinct elements

Key Takeaway

🎯 Key Insight: Sort first, then greedily assign the smallest unused value within each element's valid range

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to sort the array first, then greedily assign the smallest available value within the allowed range for each element. This greedy approach maximizes distinct elements efficiently. Best approach uses sorting with greedy assignment. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O((2k+1)ⁿ)	O(n)	Try all possible adjustment combinations for each element
Greedy with Sorting	O(n log n)	O(n)	Sort elements and greedily assign smallest available values

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible adjustment values for each element
Try every combination of adjustments
Count distinct elements in each combination
Return maximum count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Options

Create all possible adjusted values for each element

Try Combinations

Test every possible combination of adjustments

Count Distinct

Find combination with maximum distinct elements

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int generateCombinations(int** adjustments, int* sizes, int n, int index, int* current, int k) {
    if (index == n) {
        // Count distinct elements
        int count = 0;
        for (int i = 0; i < n; i++) {
            int found = 0;
            for (int j = 0; j < i; j++) {
                if (current[i] == current[j]) {
                    found = 1;
                    break;
                }
            }
            if (!found) count++;
        }
        return count;
    }
    
    int maxDistinct = 0;
    for (int i = 0; i < sizes[index]; i++) {
        current[index] = adjustments[index][i];
        int result = generateCombinations(adjustments, sizes, n, index + 1, current, k);
        if (result > maxDistinct) maxDistinct = result;
    }
    return maxDistinct;
}

int solution(int* nums, int n, int k) {
    // Generate all possible adjustments for each element
    int** adjustments = (int**)malloc(n * sizeof(int*));
    int* sizes = (int*)malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        adjustments[i] = (int*)malloc((2 * k + 1) * sizeof(int));
        sizes[i] = 2 * k + 1;
        for (int adj = -k; adj <= k; adj++) {
            adjustments[i][adj + k] = nums[i] + adj;
        }
    }
    
    int* current = (int*)malloc(n * sizeof(int));
    int result = generateCombinations(adjustments, sizes, n, 0, current, k);
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(adjustments[i]);
    }
    free(adjustments);
    free(sizes);
    free(current);
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL && n < 100) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((2k+1)ⁿ)

Each element has 2k+1 possible values, generating (2k+1)^n combinations

✓ Linear Growth

Space Complexity

O(n)

Space for storing current combination and checking distinct values

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler