Leetcode 945 Minimum Increment to Make Array Unique

Показать описание

Рекомендации по теме

Комментарии

Initially, I thought of using Next Greater to Left & Next Greater to Right concepts, & did dry run as per below written code for the test cases, [1, 2, 2], [3, 2, 1, 2, 1, 7] & [4, 4, 4, 4, 4]. According to the dry run, I got the correct answers, but when I run the test cases on leetcode, I get correct output for [1, 2, 2], but for [3, 2, 1, 2, 1, 7] & [4, 4, 4, 4, 4], it shows output of 4, which is wrong. My dry run (as per the same code) yielded correct answer, but on running on platform, it fails. Can anyone help me address this issue ? The code is :

class Solution {
private:
vector<int> NGR(vector<int>& arr, int n){
stack<int> st;
vector<int> result(n, -1);

for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && st.top() <= arr[i]) {
st.pop();
}
if (!st.empty()) {
result[i] = st.top();
}
st.push(arr[i]);
}
return result;
}
vector<int> NGL(vector<int>& arr, int n){
stack<int> st;
vector<int> result(n, -1);

for (int i = 0; i < n; i++) {
while (!st.empty() && st.top() <= arr[i]) {
st.pop();
}
if (!st.empty()) {
result[i] = st.top();
}
st.push(arr[i]);
}
return result;
}
public:
int nums) {
int n = nums.size();
vector<int> ngr = NGR(nums, n);
vector<int> ngl = NGL(nums, n);
set<int> st;
int minMoves = 0;

for(int i = 0; i < n; i++){
int num = nums[i];
if(st.find(num) == st.end()) st.insert(num);
else{
int gRight = ngr[i];
int gLeft = ngl[i];
// 4 cases
// case - 1
if(gRight == -1 && gLeft == -1){
minMoves++;
num++;
}
// case - 2
else if(min(gRight, gLeft) == -1){
minMoves += max(gRight, gLeft) + 1 - num;
num = max(gRight, gLeft) + 1;
}
// case - 3 & 4
else if(min(gRight, gLeft) != -1){
int diff = abs(gRight - gLeft);
if(diff > 1){
minMoves += min(gRight, gLeft) + 1 - num;
num = min(gRight, gLeft) + 1;
}
else if(diff == 1){
minMoves += max(gRight, gLeft) + 1 - num;
num = max(gRight, gLeft) + 1;
}
}
}
}
return minMoves;
}
};

imPriyansh

Brilliant and easy to understand. Thank you

nickx

Leetcode 945 Minimum Increment to Make Array Unique

Minimum Increment to Make Array Unique - Leetcode 945 - Python

LeetCode 945: Minimum Increment to Make Array Unique (Intuition + Greedy Algorithm Explained)

Minimum Increment to Make Array Unique ( LEETCODE || Problem 945 )

Leetcode 945 || Minimum Increment to make array unique

Minimum Increments to make array unique (LeetCode 945) | Sorting

Leetcode 945. Minimum Increment to Make Array Unique (Medium)

LeetCode 945. Minimum Increment to Make Array Unique

Minimum increment to make array unique leetcode 945 python

LeetCode 945 - Minimum Increment to Make Array Unique - Java

Minimum Increment to Make Array Unique - Leetcode 945 - Java

Leetcode 945 Minimum Increment to Make Array Unique

PART 1 - LeetCode 945 - Minimum Increment to Make Array Unique

Leetcode 945 - Minimum Increment to Make Array Unique - Python

LeetCode 945 | Minimum Increment to Make Array Unique | LeetCode Daily Challenge | Arrays | Greedy

945. Minimum Increment to Make Array Unique | Medium | Leetcode 945

[June 14, 2024, LeetCode daily] 945. Minimum Increment to Make Array Unique - Python solution

945. Minimum Increment to Make Array Unique | Greedy | Counting Sort

Leetcode 945 Minimum Increment to Make Array Unique

Leetcode 945 - Minimum Increment to Make Array Unique [14/6/24]

Minimum Increment to Make Array Unique | Leetcode #945

945. Minimum Increment to Make Array Unique | POTD Leetcode | Sorting | Explanation with Code

LeetCode soluton - 945. Minimum Increment to Make Array Unique - TypeScript and JavaScript

LeetCode Problem : 945. Minimum Increment to Make Array Unique || C++ Language || 14 June 2024

Minimum Increment to Make Array Unique | Leetcode 945 | Java | O(N)Time Complexity | Developer Coder