Minimum Operations to Make the Array Increasing

Minimum Operations to Make the Array Increasing - Problem

Array Greedy Easy

You are given an integer array nums (0-indexed). In one operation, you can choose an element of the array and increment it by 1.

For example, if nums = [1,2,3], you can choose to increment nums[1] to make nums = [1,3,3].

Return the minimum number of operations needed to make nums strictly increasing.

An array nums is strictly increasing if nums[i] < nums[i+1] for all 0 <= i < nums.length - 1. An array of length 1 is trivially strictly increasing.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: After 3 operations: [1,2,3]. Operations: increment nums[1] to 2 (1 op), increment nums[2] to 3 (2 ops).

Example 2 — Partially Sorted

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

› Output: 14

💡 Note: Transform to [1,5,6,7,8]. Operations: nums[2]: 2→6 (4 ops), nums[3]: 4→7 (3 ops), nums[4]: 1→8 (7 ops). Total: 14.

Example 3 — Already Sorted

$ Input: nums = [8]

› Output: 0

💡 Note: Single element array is already strictly increasing, no operations needed.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,1,1] where elements are not strictly increasing

Process

Increment elements to make each one greater than the previous

Output

Return total number of increment operations needed

Key Takeaway

🎯 Key Insight: Only increment elements to be exactly one more than the previous element

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is that we only need to ensure each element is strictly greater than the previous one. The greedy approach scans left to right, adjusting each element to be exactly previous + 1 when needed. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Single Pass	O(n)	O(1)	Scan left to right, adjusting each element to be minimum required
Brute Force Recursive	O(k^n)	O(n)	Try all possible ways to increment elements recursively

Greedy Single Pass — Algorithm Steps

Start from second element
If current ≤ previous, set current = previous + 1
Count operations needed for each adjustment

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Left-to-Right

Check each element against the previous one

Adjust When Needed

If current ≤ previous, increment to previous + 1

Count Operations

Sum up all increment operations needed

Code -

solution.c — C

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

int solution(int* nums, int size) {
    if (size <= 1) {
        return 0;
    }
    
    int operations = 0;
    
    for (int i = 1; i < size; i++) {
        if (nums[i] <= nums[i-1]) {
            // Need to increment nums[i] to be nums[i-1] + 1
            int needed = nums[i-1] + 1 - nums[i];
            operations += needed;
            nums[i] = nums[i-1] + 1;
        }
    }
    
    return operations;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array of n elements

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for tracking

✓ Linear Space

23.4K 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

Greedy Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler