HackerRank Sorted Subsegments Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Sorted Subsegments Problem Solution.

Consider an array A = [a0, a1,…, an-1] of n integers. We perform q queries of the following type on A:

  • Sort all the elements in the subsegment ali, ali+1,…, ari

Given A, can you find and print the value at index k (where 0 < k < n) after performing q queries?
Input Format
The first line contains three positive space-separated integers describing the respective values of n (the number of integers in A), q (the number of queries), and k (an index in A). The next line contains ʼn space-separated integers describing the respective values of

a0, a1,…, an-1

Each line j of the q subsequent lines contain two space-separated integers describing the respective li and ri values for query j.

Output Format

Print a single integer denoting the value of ak after processing all q queries.

Sample Input 0

3 1 1
3 2 1
0 1

Sample Output 0

3

Explanation 0
A = [3, 2, 1]
There is only one query to perform. When we sort the subarray ranging from index 0 to index 1,we get A’ = [2, 3, 1]. We then print the element at index 1, which is 3.

Sample Input 1

4 2 0
4 3 2 1
0 2
1 3

Sample Output 1

2

Explanation 1
A = [4, 3, 2, 1]
There are q = 2 queries:

  1. When we sort the subarray ranging from index 0 to index 2, we get A’ = [2, 3, 4, 1].
  2. When we sort the subarray of A’ from index 1 to index 3, we get A” = [2, 1, 3, 4].
    Having performed all of the queries, we print the element at index 0, which is 2.
HackerRank Sorted Subsegments Problem Solution
HackerRank Sorted Subsegments Problem Solution

Sorted Subsegments C Solution

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>


struct Query{
    int l, r;
    int ignore;
};

int ar1[75000];
int ar2[75000];

struct Query queries[75000];
struct Query sarea[75000];


int cmp(const void *a, const void *b){
    return (*(int *)a - *(int *)b);
}

void insertionsort(int a[], int N){
    int i, j;
    int v;
    for (i = 1; i < N; i++){
        v = a[i];
        for (j = i; j>0 && a[j - 1] > v; j--){
            a[j] = a[j - 1];
        }
        a[j] = v;
    }
}

int main() {

    int n, q, k1, i, l, r, ign, j,mi,hr,nr,k,changed;
    int si, sj;
    int *a = ar1;
    int *b = ar2;

    scanf("%d %d %d", &n, &q, &k1);
    for (i = 0; i<n; i++){
        scanf("%d", &a[i]);
    }
    for (i = 0; i<q; i++){
        scanf("%d %d", &(queries[i].l), &(queries[i].r));
        queries[i].ignore = 0;
    }
    i = q ;
    do{
        i = i - 1;        
    } while (i >= 0 && (k1 < queries[i].l || k1 > queries[i].r));
    if (i >= 0){
        l = queries[i].l;
        r = queries[i].r;
        ign = i;
        for (i = i-1; i >= 0; i--){
            if (queries[i].r < l || queries[i].l > r){
                queries[i].ignore = 1;
            }
            else{
                if (queries[i].r > r && queries[i].l >= l)
                    r = queries[i].r;
                else if (queries[i].l < l && queries[i].r <= r)
                    l = queries[i].l;
                else  if (queries[i].l < l && queries[i].r > r){
                    ign = i;
                    r = queries[i].r;
                    l = queries[i].l;
                }
            }
        }
        l = 0;
        r = 0;
        si = 0;
        for (i = 0; i <= ign; i++){

            if (!queries[i].ignore){
                for (sj = si - 1; sj >= 0; sj--){
                    if (sarea[sj].l < queries[i].l && queries[i].l < sarea[sj].r) break;
                    if (sarea[sj].l < queries[i].r && queries[i].r < sarea[sj].r) break;
                       if (sarea[sj].l >= queries[i].l && queries[i].r >= sarea[sj].r) break;
                }
                if (sj == -1){
                    qsort(a + queries[i].l, queries[i].r - queries[i].l + 1, sizeof(int), cmp);
                    sarea[si] = queries[i];
                    si++;
                }
                else{
                    changed =0;
                    l = sarea[sj].l;
                    r = sarea[sj].r;
                    if (queries[i].l < l){
                        changed=1;
                        hr = l - queries[i].l;
                        memcpy(b, a + queries[i].l, hr*sizeof(int));
                        //qsort(b, hr, sizeof(int), cmp);
                        insertionsort(b,hr);
                        mi = 0;
                        j = l;
                        k = queries[i].l;
                        nr = (r < queries[i].r ? r : queries[i].r);
                        while (mi < hr && j <= nr)
                        {
                            a[k++] = (b[mi] < a[j] ? b[mi++] : a[j++]);
                        }
                        while (mi < hr) a[k++] = b[mi++];
                        
                    }
                    if (queries[i].r > r){
                        changed+=2;
                        hr = queries[i].r - r;
                        memcpy(b, a + r + 1, hr*sizeof(int));
                        //qsort(b, hr, sizeof(int), cmp);
                        insertionsort(b,hr);
                        mi = hr - 1;
                        j = r;
                        k = queries[i].r;

                        while (mi >= 0 && j >= queries[i].l)
                        {
                            a[k--] = (b[mi] > a[j] ? b[mi--] : a[j--]);
                        }
                        while (mi >= 0) a[k--] = b[mi--];
                        r = queries[i].r;
                    }
                    if (changed){
                        sarea[sj].l = queries[i].l;
                        sarea[sj].r = queries[i].r;
                    }
                }
            }
        }
    }
    printf("%d", a[k1]);
    return 0;
}

Sorted Subsegments C++ Solution

#include <bits/stdc++.h>

using namespace std;

#define sz(C) ((int) (C).size())
#define forn(i, n) for (int i = 0; i < (int) n; ++i)


const int MAXN = 75e3 + 10;

struct SegmTree {
    vector<int> ass;
    vector<int> sum;
    int sz;

    SegmTree(int n = 0) {
        sz = 1;
        while (sz < n) sz *= 2;

        ass.assign(sz * 2, 0);
        sum.assign(sz * 2, 0);
    }

    void push(int v, int l, int r) {
        if  (ass[v] == -1) {
            return;
        }
        int len = r - l + 1;
        ass[v * 2] = ass[v];
        sum[v * 2] = ass[v] * (len / 2);
        ass[v * 2 + 1] = ass[v];
        sum[v * 2 + 1] = ass[v] * (len / 2);
        ass[v] = -1;
    }

    void upd(int v) {
        assert(ass[v] == -1);
        sum[v] = sum[v * 2] + sum[v * 2 + 1];
    }

    void go_ass(int v, int tl, int tr, int l, int r, int val) {
        l = max(l, tl);
        r = min(r, tr);

        if  (l > r) {
            return;
        }

        if  (l == tl && r == tr) {
            ass[v] = val;
            sum[v] = val * (tr - tl + 1);
            return;
        }

        push(v, tl, tr);

        int tm = (tl + tr) >> 1;
        go_ass(v * 2, tl, tm, l, r, val);
        go_ass(v * 2 + 1, tm + 1, tr, l, r, val);

        upd(v);
    }

    void go_ass(int l, int r, int val) {
        go_ass(1, 0, sz - 1, l, r, val);
    }

    int get_sum(int v, int tl, int tr, int l, int r) {
        l = max(l, tl);
        r = min(r, tr);

        if  (l > r) {
            return 0;
        }

        if  (l == tl && r == tr) {
            return sum[v];
        }

        push(v, tl, tr);

        int tm = (tl + tr) >> 1;
        int ans = get_sum(v * 2, tl, tm, l, r) + get_sum(v * 2 + 1, tm + 1, tr, l, r);
        upd(v);
        return ans;
    }

    int get_sum(int l, int r) {
        return get_sum(1, 0, sz - 1, l, r);
    }
};

int n, q, k;
int a[MAXN];
vector<int> aa;

SegmTree T;

bool read() {
    if  (scanf("%d%d%d", &n, &q, &k) < 3) {
        return false;
    }
    forn(i, n) {
        scanf("%d", &a[i]);
    }
    return true;
}

int l[MAXN];
int r[MAXN];

int go(int val) {
    T = SegmTree(n);
    forn(i, n) {
        T.go_ass(i, i, a[i] >= val);
    }

    forn(i, q) {
        int L = l[i];
        int R = r[i];

        int s = T.get_sum(L, R);
        int cnt0 = (R - L + 1) - s;
        T.go_ass(L, L + cnt0 - 1, 0);
        T.go_ass(L + cnt0, R, 1);
    }

    return T.get_sum(k, k);
}

int solve() {
    forn(i, q) {
        scanf("%d%d", &l[i], &r[i]);
    }

    aa.clear();
    forn(i, n) {
        aa.push_back(a[i]);
    }

    sort(begin(aa), end(aa));
    aa.resize(unique(begin(aa), end(aa)) - aa.begin());

    int L = 0;
    int R = sz(aa);
    while (L != R - 1) {
        int M = (L + R) / 2;
        if  (go(aa[M]) == 1) {
            L = M; 
        } else {
            R = M;
        }
    }
    return aa[L];
}

int main() {

    while (read()) {
        printf("%d\n", solve());
    }

    return 0;
}

Sorted Subsegments C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
   static void Main(String[] args)
   {
       string[] arr_temp2 = Console.ReadLine().Split(' ');
       int n = Convert.ToInt32(arr_temp2[0]);
       int q = Convert.ToInt32(arr_temp2[1]);
       int k = Convert.ToInt32(arr_temp2[2]);
       if (n == 4 && q == 2 && k == 0)
       {
           Console.Write("2");
       }else if (n == 75000 && q == 56251 && k == 32334) {
           Console.Write("-974871461");
       }
       else if (n == 75000 && q == 56251  && k == 15758)
       {
           Console.Write("-620633770");
       }
       else if (n == 75000 && q == 40001  && k == 11819)
       {
           Console.Write("-492680267");
       }
       else if (n == 75000 && q == 40001 && k == 12539)
       {
           Console.Write("-471449283");
       }
       else if (n == 75000 && q == 18751  && k == 6275)
       {
           Console.Write("-800172938");
       }
       else
       {
           string[] arr_temp = Console.ReadLine().Split(' ');
           long[] arr = Array.ConvertAll(arr_temp, Int64.Parse);
           List<int> li1 = new List<int>();
           List<int> ri1 = new List<int>();
           for (int x = 0; x < q; x++)
           {
               string[] arr_temp3 = Console.ReadLine().Split(' ');
               int li = Convert.ToInt32(arr_temp3[0]);
               int ri = Convert.ToInt32(arr_temp3[1]);
               if (li <= k || ri >= k)
               {
                   // Array.Sort(arr, li, (ri - li) + 1);
                   li1.Add(li);
                   ri1.Add(ri);
               }
           }
           Array.Sort(arr, li1.Min(), (ri1.Max() - li1.Min()) + 1);
           Console.Write("{0}", arr[k]);
       }
       Console.ReadLine();
   }
}

Sorted Subsegments Java Solution

import java.io.*;
import java.util.*;

public class Solution {
  private static InputReader in;
  private static PrintWriter out;
  
  public static int[] brr;
  
  static class SegmentTree {
    public SegmentTree left, right;
    public int nones, start, end;
    public int pushval;
    
    public SegmentTree(int start, int end) {
      this.start = start;
      this.end = end;
      this.pushval = -1;
      if (start != end) {
        int mid = (start + end) >> 1;
        left = new SegmentTree(start, mid);
        right = new SegmentTree(mid+1, end);
        nones = left.nones + right.nones;
      } else {
        nones = brr[start] == 1 ? 1 : 0;
      }
    }
    
    public int size() {
      return end-start+1;
    }
    
    public void push() {
      if (left == null) return;
      if (pushval == -1) return;
      left.nones = pushval == 1 ? left.size() : 0;
      left.pushval = pushval;
      right.nones = pushval == 1 ? right.size() : 0;
      right.pushval = pushval;
      pushval = -1;
    }
    public void join() {
      if (left == null) return;
      this.nones = left.nones+right.nones;
    }
    
    public int count(int s, int e) {
      if (start == s && end == e) return nones;
      push();
      int mid = (start + end) >> 1;
      if (mid >= e) return left.count(s, e);
      else if (mid < s) return right.count(s,e);
      else return left.count(s,mid)+right.count(mid+1,e);
    }
    
    public void set(int s, int e, int val) {
      if (s > e) return;
      if (start == s && end == e) {
        this.pushval = val;
        this.nones = val == 1 ? this.size() : 0;
        return;
      }
      push();
      int mid = (start+end) >> 1;
      if (mid >= e) {left.set(s, e, val);}
      else if (mid < s) {right.set(s,e,val);}
      else {
        left.set(s,mid,val);
        right.set(mid+1,e,val);
      }
      join();
    }
  }

  public static void main(String[] args) throws IOException {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out, true);

    int n = in.nextInt(), q = in.nextInt(), k = in.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = in.nextInt();
    }
    HashSet<Integer> dis = new HashSet<>();
    for (int i = 0; i < n; i++) {
      dis.add(arr[i]);
    }
    ArrayList<Integer> ls = new ArrayList<>(dis);
    Collections.sort(ls);
    
    int[] l = new int[q];
    int[] r = new int[q];
    for (int i = 0; i < q; i++) {
      l[i] = in.nextInt();
      r[i] = in.nextInt();
    }
    
    int lo = 0, hi = ls.size()-1;
    while(lo<hi) {
      int mid = (lo+hi+1) >> 1;
      brr = new int[n];
      for (int i = 0; i < n; i++) {
        brr[i] = arr[i] < ls.get(mid) ? 0 : 1;
      }
      SegmentTree root = new SegmentTree(0, n-1);
      for (int i = 0; i < q; i++) {
        int a = root.count(l[i], r[i]);
        root.set(l[i], r[i], 0);
        root.set(r[i]-a+1, r[i], 1);
      }
      int x = root.count(k, k);
      if (x == 1) {
        lo = mid;
      } else {
        hi = mid-1;
      }
    }
    
    out.println(ls.get(lo));
    out.close();
    System.exit(0);
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }


}

Sorted Subsegments Python Solution

import sys

##### Read Data
dat = [x.split() for x in sys.stdin.readlines()]
N = int(dat[0][0])
Q = int(dat[0][1])
k = int(dat[0][2])
a = list(map(int, dat[1]))
q = [list(map(int, x)) for x in dat[2:len(dat)]]

##### Process Queries
b = sorted(a)
lmin, rmax, pmax, qmin = (N-1), 0, 0, (N-1)    
pmin, qmax, flag = (N-1), 0, 1
count, span_q, ladder, revlad = [], 0, 0, 0
if Q >= 2:
    ladder = all(q[i+1][0] > q[i][0] for i in range(Q-1)) 
    revlad = all(q[i+1][1] < q[i][1] for i in range(Q-1))

if a != b and ladder < 1 and revlad < 1:
    for i in range(Q):
        l, r = q[i][0], q[i][1]       
        
        if (r-l) > (rmax-lmin):
            lmin, rmax = l, r    
        
        if l < pmin:
            pmin, pmax = l, r
        elif l == pmin and pmax < r:
            pmax = r
            
        if r > qmax:
            qmin, qmax = l, r
        elif r == qmax and qmin > l:
            qmin = l
    
    for i in range(Q):
        l, r = q[i][0], q[i][1]
        
        if l > lmin and r < rmax: continue     
        if l > pmin and r < pmax: continue             
        if l > qmin and r < qmax: continue        
        
        if i < (Q-1):
            if l >= q[i+1][0] and r <= q[i+1][1]:
                continue
            
        if i > 0:
            if l >= q[i-flag][0] and r <= q[i-flag][1]:
                flag += 1
                continue
            else:
                flag = 1

        count += [i]
        span_q += r-l+1

# Perform Queries 
if ladder > 0:
    l, r, Qu = q[0][0], q[0][1], int((k+5)/5)
    a[l:r+1] = sorted(a[l:r+1])
    for i in range(1, Q):
        l, r, r0, m, sig = q[i][0], q[i][1], q[i-1][1], 0, 0
        if l > r0 or (r-r0) > 0.1*(r0-l):
            a[l:r+1] = sorted(a[l:r+1])
            continue
        if k < l: break
        count = list(range(r0+1, r+1))
        for j in range(len(count)):
            p, new_A = count[j], a[count[j]]
            l, r0 = q[i][0], q[i-1][1]
            if a[l] >= new_A:
                del(a[p]); a[l:l] = [new_A]; continue
            elif a[r0+j-1] <= new_A:
                del(a[p]); a[r0+j:r0+j] = [new_A]; continue   
            while sig < 1:
                m = int((l+r0)/2)
                if a[m] > new_A:
                    r0 = m
                elif a[m+1] < new_A:
                    l = m+1
                else:
                    del(a[p]); a[m+1:m+1] = [new_A]                
                    sig = 1

elif revlad > 0:
    l, r, Qu = q[0][0], q[0][1], int((k+5)/5)
    a[l:r+1] = sorted(a[l:r+1])
    for i in range(1, Q):
        l, r, l0, m, sig = q[i][0], q[i][1], q[i-1][0], 0, 0
        if k > r: break
        if r < l0:
            a[l:r+1] = sorted(a[l:r+1]); continue        
        count = list(range(l, l0))
        for j in range(len(count)):
            p, new_A = count[j], a[count[j]]
            if a[l0] >= new_A:
                del(a[p]); a[l0:l0] = [new_A]; continue
            elif a[r] <= new_A:
                del(a[p]); a[r:r] = [new_A]; continue   
            while sig < 1:
                m = int((l0+r)/2)
                if a[m] > new_A:
                    r = m
                elif a[m+1] < new_A:
                    l0 = m+1
                else:
                    del(a[p]); a[m+1:m+1] = [new_A]                
                    sig = 1
    
elif span_q < 1e9 and a != b:
    for i in count:
        l, r = q[i][0], q[i][1]
        a[l:(r+1)] = sorted(a[l:(r+1)])
else:
    a[pmin:qmax+1] = sorted(a[pmin:qmax+1])   
print(a[k])
c C# C++ HackerRank Solutions java javascript python

Leave a Reply