Scale Engineer

Maximum Element After Decreasing and Rearranging

Med
#1686Time: O(N log N) The dominant operation is sorting the array, which typically takes O(N log N) time. The subsequent pass through the array takes O(N) time.Space: O(log N) or O(N) This depends on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitive types has a space complexity of O(log N) for the recursion stack of quicksort. If a copy of the array is needed, it would be O(N).
Patterns
Greedy
Algorithms
Sorting
Data structures
Array

Prompt

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.

 

Example 1:

arr

Example 2:

arr

Example 3:

Input: arr = [1,2,3,4,5]
Output: 5
Explanation: The array already satisfies the conditions, and the largest element is 5.

 

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i] <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

The core idea is that to maximize the final element, we should make the array a non-decreasing sequence. By sorting the input array, we can process the elements in increasing order. This allows us to greedily construct the target array by ensuring each element satisfies the condition arr[i] <= arr[i-1] + 1 while being as large as possible.

Algorithm

  • Sort the input array arr in non-decreasing order.
  • Set the first element arr[0] to 1 to satisfy the first condition.
  • Iterate through the array from the second element (i = 1 to n-1).
  • For each element arr[i], if it violates the condition arr[i] - arr[i-1] <= 1 (i.e., arr[i] > arr[i-1] + 1), decrease its value to arr[i-1] + 1. This is the minimal change to satisfy the condition while keeping the value as large as possible.
  • After the loop, the array is valid, and its maximum element is the last one, arr[n-1]. Return this value.

Walkthrough

This approach leverages the power of rearranging by sorting the array first. Sorting is a key step because it allows us to build the resulting array greedily and optimally.

  1. Sort the array: We sort arr in non-decreasing order. For a non-decreasing array, the condition abs(arr[i] - arr[i-1]) <= 1 simplifies to arr[i] <= arr[i-1] + 1.

  2. Set the first element: The first condition requires arr[0] to be 1. We enforce this by setting arr[0] = 1. Since the problem states all elements are positive, the original arr[0] (after sorting) is at least 1, so we only ever decrease it if it's larger than 1.

  3. Greedily adjust subsequent elements: We iterate from the second element (i = 1). For each arr[i], we must ensure it's no more than arr[i-1] + 1. If arr[i] is already within this bound, we leave it, as we want to keep values high. If arr[i] > arr[i-1] + 1, we must decrease it. To maximize the final result, we perform the minimal decrease, setting arr[i] = arr[i-1] + 1.

  4. Return the maximum: After this process, the array satisfies all conditions, and since it's non-decreasing, the maximum element is the last one, arr[arr.length - 1].

import java.util.Arrays; class Solution {    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {        Arrays.sort(arr);        arr[0] = 1;        for (int i = 1; i < arr.length; i++) {            if (arr[i] > arr[i - 1] + 1) {                arr[i] = arr[i - 1] + 1;            }        }        return arr[arr.length - 1];    }}

Complexity

Time

O(N log N) The dominant operation is sorting the array, which typically takes O(N log N) time. The subsequent pass through the array takes O(N) time.

Space

O(log N) or O(N) This depends on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitive types has a space complexity of O(log N) for the recursion stack of quicksort. If a copy of the array is needed, it would be O(N).

Trade-offs

Pros

  • The logic is intuitive and relatively easy to implement.

  • If modifying the input array is allowed, the space complexity is very low (O(log N) for sort recursion stack).

Cons

  • The time complexity is dominated by the sorting step, making it less efficient than a linear-time solution.

Solutions

public class Solution { public int MaximumElementAfterDecrementingAndRearranging ( int [] arr ) { Array . Sort ( arr ); int n = arr . Length ; arr [ 0 ] = 1 ; for ( int i = 1 ; i < n ; ++ i ) { arr [ i ] = Math . Min ( arr [ i ], arr [ i - 1 ] + 1 ); } return arr [ n - 1 ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem