Maximum Element After Decreasing and Rearranging

Maximum Element After Decreasing and Rearranging - Problem

You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:

The value of the first element in arr must be 1.
The absolute difference between any 2 adjacent elements must be less than or equal to 1. In other words, abs(arr[i] - arr[i - 1]) <= 1 for each i where 1 <= i < arr.length (0-indexed). abs(x) is the absolute value of x.

There are 2 types of operations that you can perform any number of times:

Decrease the value of any element of arr to a smaller positive integer.
Rearrange the elements of arr to be in any order.

Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.

Input & Output

Example 1 — Basic Case

$ Input: arr = [2,1,3,5,4]

› Output: 5

💡 Note: Sort to [1,2,3,4,5]. Build staircase: arr[0]=1, arr[1]=min(2,2)=2, arr[2]=min(3,3)=3, arr[3]=min(4,4)=4, arr[4]=min(5,5)=5. Maximum is 5.

Example 2 — Large Values Need Reduction

$ Input: arr = [100,1,1000]

› Output: 3

💡 Note: Sort to [1,100,1000]. Build staircase: arr[0]=1, arr[1]=min(100,2)=2, arr[2]=min(1000,3)=3. Maximum is 3.

Example 3 — Already Optimal

$ Input: arr = [1,2,3,4]

› Output: 4

💡 Note: Already sorted and valid staircase. Each element can keep its value: 1→2→3→4. Maximum is 4.

Constraints

1 ≤ arr.length ≤ 10⁵
1 ≤ arr[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with constraints to satisfy

Sort & Build

Sort and greedily build optimal staircase

Maximum Element

Return the highest element in valid arrangement

Key Takeaway

🎯 Key Insight: Sorting enables greedy construction of the tallest valid staircase

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is that sorting the array allows us to greedily build the tallest possible staircase. After sorting, each position gets the minimum of its original value or one more than the previous position. Best approach is greedy after sorting. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimal Greedy - Maximum Staircase Height	O(n log n)	O(1)	Sort and build tallest possible staircase with constraint arr[i] ≤ arr[i-1] + 1
Brute Force - Try All Arrangements	O(n! × 2^n)	O(n)	Generate all possible arrangements and decreases, check constraints, find maximum
Sort First - Greedy Construction	O(n log n)	O(1)	Sort array, then greedily build optimal staircase starting from 1

Optimal Greedy - Maximum Staircase Height — Algorithm Steps

Sort array to have best candidates first
Set arr[0] = 1 (constraint)
For i from 1 to n-1: arr[i] = min(arr[i], arr[i-1] + 1)
Return maximum element in final array

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort for Optimization

Arrange elements to maximize potential

Greedy Assignment

Each position gets min(original, prev + 1)

Maximum Height

Final element represents maximum achievable height

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* arr, int n) {
    // Sort to get optimal arrangement
    qsort(arr, n, sizeof(int), compare);
    
    // Build maximum height staircase
    arr[0] = 1;  // First must be 1
    
    for (int i = 1; i < n; i++) {
        // Greedy: take maximum possible at each step
        if (arr[i] > arr[i-1] + 1) {
            arr[i] = arr[i-1] + 1;
        }
    }
    
    return arr[n-1];  // Last element will be the maximum
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int n = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(arr, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), single pass takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only constant extra variables needed

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

892 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

Optimal Greedy - Maximum Staircase Height — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler