Minimum Increment to Make Array Unique | Leetcode #945

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

Minimum Increment to Make Array Unique.

Today we'll be looking at two potential solutions at determining the minimum increment to make array unique.

You can find the problem statement on leetcode:

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

Комментарии

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

good vid, but i didnt understand the logic

premthapa

May I ask why do you use len(A)*2? what if A = [100, 100, 1]?

shrimpo

Hi! What do you think would be the solution if every element would have a cost for increment with one unit?

mihailmihai

Can I asked why did you stop working on robin hoops?

NastyStacks

Minimum Increment to Make Array Unique | Leetcode #945

Minimum Increment to Make Array Unique - Leetcode 945 - Python

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

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 Increment to Make Array Unique | LeetCode | C++/Java/C#/Python | @codercodesofficial

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

Minimum Increment to make Array Unique #shortvideo #coding #leetcode

Codechef Starters 191 (Div.4) | Video Solutions | Smart Interviews

Minimum Increment to Make Array Unique | Sorting | Counting Sort | Leetcode 945 | codestorywithMIK

Minimum Increment to Make Array Unique.

Minimum Increment to Make Array Unique - Leetcode 945 - Java

LeetCode 945 - Minimum Increment to Make Array Unique - Java

Minimum increment to make array unique leetcode 945 python

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

LeetCode 945. Minimum Increment to Make Array Unique

#201 Minimum Increment to Make Array Unique | LeetCode POTD | GFG Solutions | 14-06-2024

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

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

945. Minimum Increment to Make Array Unique | Greedy

Minimum Increment to Make Array Unique: 3 Ways | Algorithm Deep Dive | Audio Podcast

# 14.06.2024 [945. Minimum Increment to Make Array Unique]

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

2919. Minimum Increment Operations to Make Array Beautiful || Greedy ❌ || Dynamic Programming ✅