Unique Colors Problem

Problem Statement

There are N boxes with each box i has value V[i]. These boxes are colorless initially and you are supposed to paint each box with some color. But as always, there are a few conditions which you will follow while painting the boxes.

1) For 2 boxes i and j (i<j) with color c1, there is no box k (i<k<j) which doesn’t have color c1. 2) For all boxes with same color, the difference between minimum and maximum value of box is no more than S.

Colors are costly and using so many different colors might make it look ugly. What is the minimum number of colors you will need to paint all the boxes while satisfying the above condition?

Input Format:

The first line contains two space-separated integers N, S (1≤5≤10^5,0≤S≤10^9). The second line contains N integers V[i] separated by spaces (-10^9 ≤ V[i]≤10^9).

Output Format:

Output one integer that is minimum number of colors needed.

Ans :

#include <iostream>
#include <vector>
using namespace std;

int main() {
int n, s;
cin >> n >> s;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

int count = 1, maxi = a[0], mini = a[0];
for (int i = 1; i < n; i++) {
    maxi = max(maxi, a[i]);
    mini = min(mini, a[i]);
    if (maxi - mini > s) {
        count++;
        maxi = mini = a[i];
        // saurvhathi
    }
}

cout << count;

return 0;
}

Happy Learning – If you require any further information, feel free to contact me.