Minimum cost to find minimum and remove ajdecents till array becomes empty.

thetwoface's blog

By thetwoface, history, 9 months ago, In English

The constraints are 1<n<=10⁵ and a[i]<=10⁹ Now you are given an array a. You task is to find minimum in the current sized array and remove that element and it's adjacent elements. The cost of this operation will be the minimum element choosen. Repeat this step till array becomes empty. Mathematically, for any i within array limit such that a[i] is minimum of array a, then remove a[i] and if i-1 exists remove a[i-1] and if i+1 exists a[i+1], the cost will be cost+=a[i] , the array will become {a1, a2,...ai-2,ai+2,....an} again find minimum and repeat the same till array becomes empty. NOTE: ELEMENTS NEED NOT TO BE UNIQUE. IF THERE ARE MULTIPLE MINIMIUMS CHOOSE THE ONE WITH LOWEST INDEX

-6

thetwoface
9 months ago
20

Comments (20)

Write comment?

thetwoface

9 months ago, hide # |

Auto comment: topic has been updated by thetwoface (previous revision, new revision, compare).

→ Reply

Ayush_Raj100

9 months ago, hide # |

What if multiple minimum exists in the array eg {2,3,6,3,4,2,2} , here min. 2 appears 3 times , do we have to remove from all occurances and its adjacent elements or do we have to choose anyone of them . Another doubt , is it mentioned in the problem that all the elements in the array are unique ?

→ Reply

thetwoface

9 months ago, hide # ^ |

If multiple minimums exists choose the one with the lowest index.

→ Reply

Ayush_Raj100

9 months ago, hide # ^ |

← Rev. 2 →

Edit :- I now realized my soln doesn't actually shift the element after deletions hence it won't give correct result ,although someone commented the correct soln. using doubly linked list below.

solved using segtree

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;
const int N = 3e5 + 5;
const int INF = 1e9;
const int M = 20;
ll n;
vector<int> arr(N);
vector<int> sg(4*N);
void update(int s,int e,int index,int update_index,int update_val){
    if(s==e){
        sg[index]=sg[index]+update_val;
        return;
    }
    int mid = (s+e)/2;
    if(update_index<=mid){
        update(s,mid,2*index,update_index,update_val);
    }else{
        update(mid+1,e,2*index+1,update_index,update_val);
    }
    sg[index] = sg[2*index]+sg[2*index +1];
}
int query(int s,int e,int index,int k){
    if(s==e){
        return s;
    }
    int mid = (s+e)/2;
    if(sg[2*index]>=k){
        return query(s,mid,2*index,k);
    }else{
        return query(mid+1,e,2*index+1,k-sg[2*index]);
    }
}
void solve(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>arr[i];
    set<int> st;
    for(int i=0;i<n;i++){
        st.insert(arr[i]);
    }
    map<int,int> mpp;
    int idx =1;
    for(auto it:st){
        mpp[it]=idx;
        idx++;
    }
    // stores all the indices of a num 
    vector<pair<int,int>> narr(n);
    for(int i=0;i<n;i++){
        narr[i]={mpp[arr[i]],arr[i]};
        //narr[i].second stores the cost
    }
    unordered_map<int,set<int>> data;
    for(int i=0;i<n;i++){
        int num=narr[i].first;
        data[num].insert(i);
    }
    for(int i=0;i<n;i++){
        update(0,N,1,narr[i].first,1);
    }
    ll cost = 0;
    vector<bool> used(n,false);
    while(sg[1]>0){
        int curr_min = query(0,N,1,1);
        update(0,N,1,curr_min,-1);
        int idx = *data[curr_min].begin();
        data[curr_min].erase(data[curr_min].begin());
        cost+=narr[idx].second;
        used[idx]=true;
        if(idx>0){
            int min_adj1 = narr[idx-1].first;
            if(used[idx-1]==false){
                update(0,N,1,min_adj1,-1);
                used[idx-1]=true;
                data[min_adj1].erase(data[min_adj1].find(idx-1));
            }
        }
        if(idx<n-1){
            int min_adj2 = narr[idx+1].first;
            if(used[idx+1]==false){
                update(0,N,1,min_adj2,-1);
                used[idx+1]=true;
                data[min_adj2].erase(data[min_adj2].find(idx+1));
            }
        }
    }
    cout<<cost<<"\n";
}

int main(){
 ios::sync_with_stdio(false);
    cin.tie(nullptr);   
 int t =1;
 //cin>>t;
 while(t--)	solve();
return 0;}

→ Reply

thetwoface

9 months ago, hide # ^ |

Is this correct! Well i dun think, cause I tried implementing it using segment tree but it doesn't shift indices as you mentioned.

→ Reply

thetwoface

9 months ago, hide # |

Auto comment: topic has been updated by thetwoface (previous revision, new revision, compare).

→ Reply

jdoe73x

9 months ago, hide # |

Sorting + Doubly Linked List

long long solve(const vector<int>& a) {
    const int n = (int)a.size();
    vector<int> idx(n), left(n), right(n);
    iota(idx.begin(), idx.end(), 0);
    iota(left.begin(), left.end(), -1);
    iota(right.begin(), right.end(), 1);
    stable_sort(idx.begin(), idx.end(), [&](int i, int j) {return a[i] < a[j];});
    vector<bool> removed(n);
    long long ans = 0;
    for (const auto& i : idx) {
        if (removed[i])
            continue;
        removed[i] = true;
        ans += a[i];
        if (left[i] != -1) {
            removed[left[i]] = true;
            left[i] = left[left[i]];
        }
        if (right[i] != n) {
            removed[right[i]] = true;
            right[i] = right[right[i]];
        }
        if (left[i] != -1)
            right[left[i]] = right[i];
        if (right[i] != n)
            left[right[i]] = left[i];
    }
    return ans;
}

→ Reply

dsogari

9 months ago, hide # ^ |

← Rev. 3 →

Is the linked list actually necessary? I believe this would be equivalent:

Code

long long solve(const vector<int>& a) {
    const int n = (int)a.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    stable_sort(idx.begin(), idx.end(), [&](int i, int j) {return a[i] < a[j];});
    vector<bool> removed(n);
    long long ans = 0;
    for (const auto& i : idx) {
        if (removed[i])
            continue;
        removed[i] = true;
        ans += a[i];
        if (i > 0)
          removed[i - 1] = true;
        if (i < n - 1)
          removed[i + 1] = true;
    }
    return ans;
}

EDIT: Oh, my mistake. I didn't realize the elements need to be shifted. Sorry about that.

However, if the constraint about "lowest index" did not exist, the problem would be a little bit harder to solve.

→ Reply

thetwoface

9 months ago, hide # ^ |

This won't work as after every operation, the array will shrink so the indices. Hope this makes sense.

→ Reply

Lever

9 months ago, hide # |

← Rev. 3 →

apologies if im misreading but can we not just

Spoiler

→ Reply

thetwoface

9 months ago, hide # ^ |

← Rev. 2 →

No the min Heap approach won't work. The logic behind is if you use min heap/ priority queue still you can't update indices, as array shrinks indices will change.

→ Reply

Lever

9 months ago, hide # ^ |

yeah i just noticed i edited it

→ Reply

thetwoface

9 months ago, hide # ^ |

I think jdoe73x has given the promising code. you could check this out in the initial comments of this blog.

→ Reply

Lever

9 months ago, hide # ^ |

nah I'm trying to solve it myself, but could you provide some polygon package or send link to leetcode (if the OA is taken off lc) so I could submit, im pretty sure of the DSU idea

→ Reply

thetwoface

9 months ago, hide # ^ |

← Rev. 2 →

You can generate random numbers and try for array of size 600000. If it works then fine. But remember the problem conditions.

→ Reply

Lever

9 months ago, hide # ^ |

← Rev. 2 →

thats not the issue, the issue is checking it

also here is my general implementation

Spoiler

//
// Created by lever on 7/9/2025.
//
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
using ll=long long;
#define iter(i, n) for(int i = 0; i < n; i++)
#define rngIt(n, m, s) if(n>m){for(int i = n-1; i >= m-1; i-=s)}else{for(int i = n; i < m; i+=s)}
#define it(arr) for(ll i : arr) std::cout << i << ' '; cout << '\n';
#define itB(arr, a) for(int i = 0; i < a; i++) std::cout << arr[i] << ' '; cout << '\n';
#define printl(s) cout<<s<<endl;
#define MOD(a, b) ((((a) % (b)) + (b)) % (b))
#define endl "\n";
struct UF {
    int cnt;
    vector<int> id, size;

    UF(int n) {
        cnt = n;
        id.resize(n);
        size.resize(n);
        for (int i = 0; i < n; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    int find(int p) {
        if (p == id[p]) return p;
        return id[p] = find(id[p]);
    }

    bool join(int p, int q) {
        p = find(p);
        q = find(q);
        if (p == q) return false;
        if (size[p] > size[q]) {
            id[q] = p;
            size[p] += size[q];
        } else {
            id[p] = q;
            size[q] += size[p];
        }
        cnt--;
        return true;
    }
};
void test()
{
    int n; cin>>n;
    ll sm = 0;
    vector<int>arr(n);
    priority_queue<pair<int,int>>pq;
    UF dsu(n);
    vector<bool>vis(n);
    vector<int>l(n),r(n);
    iter(i,n)
    {
        l[i]=i;
        r[i]=i;
    }
    iter(i,n)
    {
        pq.push({i,arr[i]});
    }
    auto cmp = [](pair<int,int>a, pair<int,int>b){if(a.second==b.second){return a.first<a.second;} return a.second<b.second;};
    while(!pq.empty())
    {
        auto [a,b] = pq.top(); pq.pop();
        if(vis[a])continue;
        sm+=b;
        vis[a] = true;
        if(a>0)
        {
            int le = l[dsu.find(a-1)];
            if(vis[a-1])dsu.join(dsu.find(a-1),a);
            l[dsu.find(a)]=le-1;
        }
        if(a<n-1)
        {
            int ri = r[dsu.find(a+1)];
            if(vis[a+1])dsu.join(dsu.find(a+1),a);
            r[dsu.find(a)]=ri+1;
        }
        if(l[dsu.find(a)]>=0)
        {
            int la=l[dsu.find(a)];
            vis[la]=true;
            dsu.join(la,dsu.find(la+1));
            l[dsu.find(a)]--;
        }
        if(r[dsu.find(a)<n])
        {
            int la = r[dsu.find(a)];
            vis[la]=true;
            dsu.join(la,dsu.find(la-1));
            r[dsu.find(a)]++;
        }
    }
    printl(sm)
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t; cin>>t;
    iter(i,t){test();}
    return 0;
}

→ Reply

thetwoface

9 months ago, hide # ^ |

Check for a={10 4 8 3 1 5 8 3 1 6 2 5 1 7} the answer is 9.

→ Reply

Lever

9 months ago, hide # ^ |

Thanks i think i got it, here

Spoiler

//
// Created by lever on 7/9/2025.
//
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define iter(i, n) for(int i = 0; i < n; i++)
#define rngIt(n, m, s) if(n>m){for(int i = n-1; i >= m-1; i-=s)}else{for(int i = n; i < m; i+=s)}
#define it(arr) for(ll i : arr) std::cout << i << ' '; cout << '\n';
#define itB(arr, a) for(int i = 0; i < a; i++) std::cout << arr[i] << ' '; cout << '\n';
#define printl(s) cout<<s<<endl;
#define MOD(a, b) ((((a) % (b)) + (b)) % (b))
#define endl "\n";
struct UF {
    int cnt;
    vector<int> id, size;

    UF(int n) {
        cnt = n;
        id.resize(n);
        size.resize(n);
        for (int i = 0; i < n; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    int find(int p) {
        if (p == id[p]) return p;
        return id[p] = find(id[p]);
    }

    bool join(int p, int q) {
        p = find(p);
        q = find(q);
        if (p == q) return false;
        if (size[p] > size[q]) {
            id[q] = p;
            size[p] += size[q];
        } else {
            id[p] = q;
            size[q] += size[p];
        }
        cnt--;
        return true;
    }
};
void test()
{
    int n; cin>>n;
    ll sm = 0;
    vector<int>arr(n);
    iter(i,n)
    {
        cin>>arr[i];
    }
    auto cmp = [](pair<int,int>a, pair<int,int>b){if(a.second==b.second){return a.first>b.first;} return a.second>b.second;};
    priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)>pq(cmp);
    UF dsu(n);
    vector<bool>vis(n);
    vector<int>l(n),r(n);
    iter(i,n)
    {
        l[i]=i-1;
        r[i]=i+1;
    }
    iter(i,n)
    {
        pq.push({i,arr[i]});
    }
    while(!pq.empty())
    {
        auto [a,b] = pq.top(); pq.pop();
        if(vis[a])continue;
        sm+=b;
        //printl("add "<<b)
        vis[a] = true;
        if(a>0)
        {
            int le = l[dsu.find(a-1)];
            if(vis[a-1])
            {
                dsu.join(dsu.find(a-1),a);
                l[dsu.find(a)]=le;
            }
        }
        if(a<n-1)
        {
            int ri = r[dsu.find(a+1)];
            if(vis[a+1])
            {
                dsu.join(dsu.find(a+1),a);
                r[dsu.find(a)]=ri;
            }
        }
        if(l[dsu.find(a)]>=0)
        {
            int la=l[dsu.find(a)];
            vis[la]=true;
            dsu.join(la,dsu.find(la+1));
            l[dsu.find(a)]--;
        }
        if(r[dsu.find(a)]<n)
        {
            int la = r[dsu.find(a)];
            vis[la]=true;
            dsu.join(la,dsu.find(la-1));
            r[dsu.find(a)]++;
        }
        //it(vis)
    }
    printl(sm)
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t; cin>>t;
    iter(i,t){test();}
    return 0;
}

→ Reply