.jpg)
Find Lexicographically Smallest Array After Operations
Problem Statement
You are given:
- An integer array nums
- An integer k
Operation allowed:
- For any index i, you can replace nums[i] with nums[i] + k any number of times (including 0).
Return the lexicographically smallest array possible after any number of operations.
Example 1
Input
nums = [3,7,1], k = 3
Output
[0,4,1]
Explanation:
- You can decrease 3 → 0, 7 → 4, 1 → 1 modulo k.
- Resulting array [0,4,1] is lexicographically smallest.
Example 2
Input
nums = [1,2,3], k = 2
Output
[1,0,1]
Explanation:
- Reduce each element modulo k to get smallest prefix.
Why This Problem Is Important
- Tests modular arithmetic
- Tests greedy strategy for lexicographic order
- Asked in LeetCode contests / Google / Amazon
- Useful for problems with modulo operations and array transformations
Key Observation
- For each element nums[i], the final value modulo k must be in [0, k-1].
- For lexicographically smallest array:
- Process elements from left to right
- Make each element as small as possible using +k operations
- Handle carry if necessary (like modular adjustments)
Approach 1: Modular Reduction + Greedy
Idea
- Convert each nums[i] to nums[i] % k
- Traverse left → right
- If previous value > current, increase current by k as many times as needed
- Resulting array is lexicographically smallest
Time and Space Complexity
- Time: O(n)
- Space: O(n) or O(1) if in-place
Python
def lexSmallestArray(nums, k):
n = len(nums)
res = nums[:]
# Step 1: take modulo
for i in range(n):
res[i] %= k
# Step 2: make non-decreasing
for i in range(1, n):
if res[i] < res[i - 1]:
diff = res[i - 1] - res[i]
increment = ((diff + k - 1) // k) * k
res[i] += increment
return res
# Driver
nums = [7, 3, 5, 8]
k = 3
print(lexSmallestArray(nums, k))
C++
#include
#include
using namespace std;
vector lexSmallestArray(vector& nums, int k) {
int n = nums.size();
vector res = nums;
for (int i = 0; i < n; i++)
res[i] %= k;
for (int i = 1; i < n; i++) {
if (res[i] < res[i - 1]) {
int diff = res[i - 1] - res[i];
int increment = ((diff + k - 1) / k) * k;
res[i] += increment;
}
}
return res;
}
int main() {
vector nums = {7, 3, 5, 8};
int k = 3;
vector ans = lexSmallestArray(nums, k);
for (int x : ans)
cout << x << " ";
return 0;
}
Java
import java.util.*;
class Solution {
public int[] lexSmallestArray(int[] nums, int k) {
int n = nums.length;
int[] res = Arrays.copyOf(nums, n);
for (int i = 0; i < n; i++)
res[i] %= k;
for (int i = 1; i < n; i++) {
if (res[i] < res[i - 1]) {
int diff = res[i - 1] - res[i];
int increment = ((diff + k - 1) / k) * k;
res[i] += increment;
}
}
return res;
}
public static void main(String[] args) {
Solution obj = new Solution();
int[] nums = {7, 3, 5, 8};
int k = 3;
int[] ans = obj.lexSmallestArray(nums, k);
for (int x : ans)
System.out.print(x + " ");
}
}
JavaScript
function lexSmallestArray(nums, k) {
const res = nums.slice();
for (let i = 0; i < res.length; i++)
res[i] %= k;
for (let i = 1; i < res.length; i++) {
if (res[i] < res[i - 1]) {
let diff = res[i - 1] - res[i];
let increment = Math.ceil(diff / k) * k;
res[i] += increment;
}
}
return res;
}
// Driver
console.log(lexSmallestArray([7, 3, 5, 8], 3));
✅ C#
using System;
class Solution {
public int[] LexSmallestArray(int[] nums, int k) {
int n = nums.Length;
int[] res = (int[])nums.Clone();
for (int i = 0; i < n; i++)
res[i] %= k;
for (int i = 1; i < n; i++) {
if (res[i] < res[i - 1]) {
int diff = res[i - 1] - res[i];
int increment = ((diff + k - 1) / k) * k;
res[i] += increment;
}
}
return res;
}
static void Main() {
Solution obj = new Solution();
int[] nums = {7, 3, 5, 8};
int k = 3;
int[] ans = obj.LexSmallestArray(nums, k);
foreach (int x in ans)
Console.Write(x + " ");
}
}
Output
[1, 3, 5, 5]
Final Summary
- Modular reduction is key (nums[i] % k)
- Adjust elements greedily left → right
- Handle carry with +k to maintain lexicographical order
- Optimal time: O(n)
- Works in all languages with minimal code
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.png)
