 # SORTARRAY - Editorial

Author: Prasant Kumar
Tester: Harris Leung
Editorialist: Nishank Suresh

2076

# PREREQUISITES:

Dynamic programming

# PROBLEM:

You have an array A. In one move, you can choose two indices i and j with i \leq j and A_i = A_j, and set every element in the segment [i, j] to A_i.

Find the minimum number of moves required to sort A, or report that it isn’t possible.

# EXPLANATION:

This problem can be solved with the help of dynamic programming.

Let dp_i denote the minimum number of moves requred to sort the first i elements of A. We want to compute dp_N.

The transitions are as follows:

Transitions
• First, if A_i \geq A_{i-1}, we can use dp_{i-1} moves to sort the first i-1 elements, and that automatically makes the first i elements sorted.
• Second, we can try to apply a move that ends at position i.
• If we choose the starting position of this move to be index j, the cost is dp_j + 1, since we require dp_j moves to sort the first j elements after making this move. Note that we can only choose an index j such that A_i = A_j.
• So, the cost of this transition is the minimum value of dp_j + 1 across all indices j \lt i with A_j = A_i
• Finally, dp_i is the minimum of the above two cases. For convenience, define dp_i = \infty (where \infty denotes some large value, say 10^9) if the first i elements cannot be sorted.

The above transitions give us a solution in \mathcal{O}(N^2), which is too slow. However, note that:

• The first case is always \mathcal{O}(1) and doesn’t really need to be optimized
• The second case is the one that might take \mathcal{O}(N). However, we are constrained to look at only those indices j \lt i such that A_j = A_i, and want the minimum dp_j across these indices.
• So, we can simply maintain an array mn, where mn_x denotes the minimum value of dp_j across all indices with A_j = x that we have seen so far.
• Updating mn is simple: once we have computed dp_i for an index i, simply set mn_{A_i} \gets \min(mn_{A_i}, dp_i)

With this optimization, our solution is now \mathcal{O}(N).

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Setter's code (C++)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
#define int long long
#define endl "\n"
using namespace __gnu_pbds;

signed main(){
ios_base::sync_with_stdio(0) , cin.tie(0);
int t;cin>>t;
while(t--){
int n;cin>>n;
int arr[n];
vector<int> op(n+1,1e9),dp(n+1,1e9);

for(int i=0;i<n;i++){
cin>>arr[i];
}

dp=0;
op[arr]=0;

for(int i=1;i<n;i++){
if(arr[i-1]<=arr[i]){
dp[i]=dp[i-1];
}
dp[i]=min(dp[i],1+op[arr[i]]);
op[arr[i]]=min(op[arr[i]],dp[i]);
}

cout<<(dp[n-1]<=n?dp[n-1]:-1)<<endl;
}

return 0;
}

Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+1;
int n;
ll a[N],dp[N];
void solve(){
cin >> n;
map<ll,int>f;
for(int i=1; i<=n ;i++){
cin >> a[i];
dp[i]=1e9;
if(a[i]>=a[i-1]) dp[i]=dp[i-1];
if(f[a[i]]<0){
ll s=f[a[i]]+1+(int)1e9;
dp[i]=min(dp[i],s);
}
ll s=dp[i]-1e9;
if(f[a[i]]>s) f[a[i]]=s;
}
if(dp[n]>=1e9) cout << "-1\n";
else cout << dp[n] << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;while(t--) solve();
}

Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
ios::sync_with_stdio(false); cin.tie(0);

const int inf = 1e7;
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<int> dp(n, inf); dp = 0;
vector<int> best(n+1, inf); best[a] = 0;
for (int i = 1; i < n; ++i) {
if (a[i] >= a[i-1]) dp[i] = dp[i-1];
dp[i] = min(dp[i], best[a[i]] + 1);
if (a[i-1] <= a[i]) best[a[i]] = min(best[a[i]], dp[i-1]);
}
if (dp[n-1] < n) cout << dp[n-1] << '\n';
else cout << -1 << '\n';
}
}

2 Likes

Well, we are choosing the optimal calculated value for A[i] for each relaxation, won’t the minimum index of A[i] give the optimal value?

Like, A = [ 4, 2, 4, 1, 2, 4 ]
For the last 4, why will the first 4 not give the optimal value?

Help me out with a test case, please!!

1 Like

Consider A = [1, 3, 2, 1, 2, 3, 2]. If you match the last 2 with the first 2, it becomes impossible to sort the array. Instead, you have to match it with the second 2 and then match the 1's, for a final array of [1, 1, 1, 1, 2, 2, 2].

4 Likes