HackerRank Sorted Subsegments Problem Solution

HackerRank Sorted Subsegments Problem Solution

Posted on By Yashwant Parihar No Comments on HackerRank Sorted Subsegments Problem Solution

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 Tags:, , , , , ,

Related Posts

HackerRank Fairy Chess Problem Solution HackerRank Fairy Chess Problem Solution c
HackerRank Journey Scheduling Problem Solution HackerRank Journey Scheduling Problem Solution c
HackerRank Missing Numbers Problem Solution HackerRank Missing Numbers Problem Solution c
HackerRank String Similarity Problem Solution HackerRank String Similarity Problem Solution c
HackerRank Chocolate Feast Problem Solution HackerRank Chocolate Feast Problem Solution c
HackerRank Robot Problem Solution HackerRank Robot Problem Solution c

Leave a Reply

Your email address will not be published. Required fields are marked *