Minimum Operations to Make the Array Increasing solution and explanation
Google
9 more videos on this problem
Leetcode 1827. Minimum Operations to Make the Array Increasing #biweekly contestCode with Alisha · 5:31 · 15K views
LeetCode 1827: Minimum Operations to Make the Array Increasing: Python EasyHashem Alsaket · 3:05 · 650 views
1827. Minimum Operations to Make the Array Increasing (Leetcode Easy)Programming Live with Larry · 2:45 · 560 views
LeetCode 1827 : Minimum Operations to Make the Array Increasing | Solution in JAVAAmit Manjarly · 5:55 · 349 views
LeetCode 1827 : Minimum Operations to Make the Array Increasing | Solution in C++Amit Manjarly · 4:52 · 208 views
LeetCode 1827 | Minimum Operations to Make the Array Increasing | Comparison | JavaSleepy Cracker · 2:13 · 161 views
Minimum Operations to Make the Array Increasing | Leetcode 1827 | Approach + Code with explanation.Pirai's Academy · 6:41 · 128 views
1827. Minimum Operations to Make the Array Increasing || leetcode greedy || MASTER GREEDYKodeCipher · 8:48 · 30 views
Leetcode - 1827. Minimum Operations to Make the Array Increasing | Live SolutionKrispy Coding · 3:45 · 24 views
LeetCode 1827: Minimum Operations to Make the Array IncreasingAlitaCode · 28:04 · 3 views
The problem
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 incrementnums[1]to makenums = [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.
Example 1:
Input: nums = [1,1,1] Output: 3 Explanation: You can do the following operations: 1) Increment nums[2], so nums becomes [1,1,2]. 2) Increment nums[1], so nums becomes [1,2,2]. 3) Increment nums[2], so nums becomes [1,2,3].
Example 2:
Input: nums = [1,5,2,4,1] Output: 14
Example 3:
Input: nums = [8] Output: 0
Constraints:
1 <= nums.length <= 50001 <= nums[i] <= 104
Approach overview
Problem Overview: You are given an integer array nums. In one operation, you can increment any element by 1. The goal is to make the array strictly increasing with the minimum number of operations.
Approach 1: Iterative Adjustment (Greedy) (Time: O(n), Space: O(1))
The most direct solution is a greedy scan from left to right. For every index i, the value must be strictly greater than the previous element nums[i-1]. If nums[i] is already greater, continue. Otherwise, increment it until it becomes nums[i-1] + 1. The number of increments required is (nums[i-1] + 1 - nums[i]), which you add to the operation count. Then update the current element to the new value so the next comparison remains valid.
This works because the smallest valid value for each position is always previous + 1. Any larger increase would only add unnecessary operations. The algorithm performs a single pass through the array and modifies values greedily, making it optimal for problems involving monotonic constraints on an array. Time complexity is O(n) and space complexity is O(1).
Approach 2: Difference Array Method (Time: O(n), Space: O(n))
This method models the required increments using a difference-style adjustment. Instead of directly modifying the array, compute how far each element is from the minimum valid value needed to maintain a strictly increasing sequence. For each index i, the expected minimum value is max(nums[i], prev + 1). The difference between the expected value and the original value represents the number of increments needed.
You can store these increments in an auxiliary structure (similar to a difference or adjustment array) and accumulate them while tracking the running valid value. This approach separates calculation from mutation, which can help when the original array must remain unchanged. The algorithm still performs a single linear pass, so the time complexity remains O(n), while storing adjustments increases the space complexity to O(n). The logic still relies on a greedy decision: always raise each element to the smallest value that keeps the sequence strictly increasing.
Recommended for interviews: The Iterative Adjustment (Greedy) approach is the expected solution. Interviewers look for the key observation that each element only needs to become previous + 1 when the order breaks. Demonstrating the greedy reasoning and implementing the single-pass O(n) solution shows strong understanding of array traversal and constraint maintenance.
Approach 1: Iterative Adjustment
This approach involves iterating through the array and ensuring each element is greater than the previous one by directly modifying the array elements. We keep track of how many operations are needed to achieve this and return the total operations as the result.
def min_operations(nums):
operations = 0
for i in range(1, len(nums)):
if nums[i] <= nums[i - 1]:
operations += (nums[i - 1] - nums[i] + 1)
nums[i] = nums[i - 1] + 1
return operationsclass Solution {
public int minOperations(int[] nums) {
int operations = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] <= nums[i - 1]) {
operations += (nums[i - 1] - nums[i] + 1);
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}
}#include <vector>
using namespace std;
int minOperations(vector<int>& nums) {
int operations = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] <= nums[i - 1]) {
operations += (nums[i - 1] - nums[i] + 1);
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}function minOperations(nums) {
let operations = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] <= nums[i - 1]) {
operations += (nums[i - 1] - nums[i] + 1);
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}#include <stdio.h>
int minOperations(int* nums, int numsSize) {
int operations = 0;
for (int i = 1; i < numsSize; i++) {
if (nums[i] <= nums[i - 1]) {
operations += (nums[i - 1] - nums[i] + 1);
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}public class Solution {
public int MinOperations(int[] nums) {
int operations = 0;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] <= nums[i - 1]) {
operations += (nums[i - 1] - nums[i] + 1);
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}
}In Python, we iterate from the second element onward, adjusting any element that isn't strictly greater than its predecessor and counting how many operations are made.
Time Complexity: O(n), with n as the number of elements.
Space Complexity: O(1), through in-place changes.
Approach 2: Difference Array Method
This method involves calculating differences between consecutive elements. If any difference is not positive, operations are added to make it positive, and we update the current element. This approach implicitly highlights where and how much adjustment is needed to ensure array elements strictly increase.
def min_operations(nums):
operations = 0
for i in range(1, len(nums)):
difference = nums[i] - nums[i - 1]
if difference <= 0:
operations += (-difference + 1)
nums[i] = nums[i - 1] + 1
return operationsclass Solution {
public int minOperations(int[] nums) {
int operations = 0;
int difference;
for (int i = 1; i < nums.length; i++) {
difference = nums[i] - nums[i - 1];
if (difference <= 0) {
operations += (-difference + 1);
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}
}#include <vector>
using namespace std;
int minOperations(vector<int>& nums) {
int operations = 0;
int difference;
for (int i = 1; i < nums.size(); i++) {
difference = nums[i] - nums[i - 1];
if (difference <= 0) {
operations += (-difference + 1);
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}function minOperations(nums) {
let operations = 0;
for (let i = 1; i < nums.length; i++) {
const difference = nums[i] - nums[i - 1];
if (difference <= 0) {
operations += (-difference + 1);
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}#include <stdio.h>
int minOperations(int* nums, int numsSize) {
int operations = 0;
int difference;
for (int i = 1; i < numsSize; i++) {
difference = nums[i] - nums[i - 1];
if (difference <= 0) {
operations += (-difference + 1);
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}public class Solution {
public int MinOperations(int[] nums) {
int operations = 0;
int difference;
for (int i = 1; i < nums.Length; i++) {
difference = nums[i] - nums[i - 1];
if (difference <= 0) {
operations += (-difference + 1);
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}
}Using Python, the implementation calculates necessary changes based on consecutive element differences, ensuring minimal operations by adjusting only when required.
Time Complexity: O(n), due to single scan of the array.
Space Complexity: O(1), as modifications occur directly in list elements.
Approach 3: Single Pass
We use a variable mx to record the maximum value of the current strictly increasing array, initially mx = 0.
Traverse the array nums from left to right. For the current element v, if v \lt mx + 1, we need to increase it to mx + 1 to ensure the array is strictly increasing. Therefore, the number of operations we need to perform this time is max(0, mx + 1 - v), which is added to the answer, and then we update mx=max(mx + 1, v). Continue to traverse the next element until the entire array is traversed.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function minOperations(nums: number[]): number {
let ans = 0;
let max = 0;
for (const v of nums) {
ans += Math.max(0, max + 1 - v);
max = Math.max(max + 1, v);
}
return ans;
}func minOperations(nums []int) (ans int) {
mx := 0
for _, v := range nums {
ans += max(0, mx+1-v)
mx = max(mx+1, v)
}
return
}impl Solution {
pub fn min_operations(nums: Vec<i32>) -> i32 {
let mut ans = 0;
let mut max = 0;
for &v in nums.iter() {
ans += (0).max(max + 1 - v);
max = v.max(max + 1);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Adjustment | Time Complexity: O(n), with n as the number of elements. |
| Difference Array Method | Time Complexity: O(n), due to single scan of the array. |
| Single Pass | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Adjustment (Greedy) | O(n) | O(1) | Best general solution; single pass and constant memory |
| Difference Array Method | O(n) | O(n) | Useful when you want to track increments separately without mutating the original array |
Frequently asked questions
Is Minimum Operations to Make the Array Increasing easy or hard?
Minimum Operations to Make the Array Increasing is classified as an Easy problem on LeetCode with a high acceptance rate of about 81%. The main challenge is recognizing the greedy observation that each element only needs to be raised to previous + 1.
Minimum Operations to Make the Array Increasing Python/Java solution
In Python or Java, iterate from index 1 to n-1 and compare each element with the previous one. If the current value is not strictly greater, compute the difference needed to make it previous + 1 and add that to the operation count. Update the current value and continue the loop.
How to solve Minimum Operations to Make the Array Increasing in O(n)?
Iterate through the array while maintaining the previous valid value. If nums[i] is less than or equal to the previous element, increment it to previous + 1 and add the difference to the operation count. Update the previous value and continue scanning. This greedy strategy ensures the minimum number of increments in a single pass.
What is the best approach for Minimum Operations to Make the Array Increasing?
The greedy iterative adjustment approach is the best solution. Traverse the array once and ensure each element is strictly greater than the previous element. If nums[i] <= nums[i-1], increment it to nums[i-1] + 1 and add the difference to the operation count. This runs in O(n) time and O(1) space.
Is Minimum Operations to Make the Array Increasing asked at Google/Amazon/Meta?
Problems involving greedy array adjustments and monotonic constraints appear frequently in interviews at companies like Amazon, Google, and Meta. Variants that require making sequences strictly increasing or non-decreasing using minimal operations are common interview patterns.
What data structure is used in Minimum Operations to Make the Array Increasing?
The primary data structure is a simple array traversal. The solution relies on greedy logic rather than complex structures like heaps or hash maps. Only variables for tracking the previous value and total operations are required.
What is the time complexity of Minimum Operations to Make the Array Increasing?
The optimal solution runs in O(n) time because the array is scanned exactly once. Each element is compared with the previous element and adjusted if necessary. Space complexity is O(1) since only a few variables are used to track the previous value and total operations.