Sponsored
Sponsored
This approach involves sorting the array first. After sorting, we iterate over the array from the first element onwards, setting each element to be the minimum between its current value and the value of the previous element plus 1. This ensures the conditions are met, i.e., the first element is 1 and the difference between adjacent elements is <= 1.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we modify the array in place.
1#include <stdio.h>
2#include <stdlib.h>
3
4// Comparator function for qsort
5int cmp(const void* a, const void* b) {
6 return (*(int*)a - *(int*)b);
7}
8
9int maxElementAfterDecreasingAndRearranging(int* arr, int arrSize) {
10 qsort(arr, arrSize, sizeof(int), cmp);
11 arr[0] = 1;
12 for (int i = 1; i < arrSize; i++) {
13 arr[i] = arr[i] < arr[i-1] + 1 ? arr[i] : arr[i-1] + 1;
14 }
15 return arr[arrSize - 1];
16}
17
18int main() {
19 int arr[] = {100, 1, 1000};
20 int length = sizeof(arr) / sizeof(arr[0]);
21 int result = maxElementAfterDecreasingAndRearranging(arr, length);
22 printf("%d", result);
23 return 0;
24}We first sort the array using qsort. Then, starting from the first index (0), we set it to 1 as the condition requires. For every subsequent element, we ensure that it is either its current value or the previous element + 1, whichever is smaller. This ensures the absolute difference between adjacent elements is at most 1.
This approach leverages the counting sort technique which avoids sorting the entire array directly. Instead, it uses a frequency array to count occurrences of each element. Then, reconstruct the final array by checking counts and adjusting values accordingly to ensure the maximum element is achieved while meeting the constraints.
Time Complexity: O(n), due to the pass over the array to count elements.
Space Complexity: O(n), primarily due to the count array.
In this Java solution, an iteration across the input array fills the count array, tracking how often each value appears. This count data helps set the elements to their maximum feasible values while respecting the constraints.