Problem

Submissions

Hints & solutions

Discuss

Team Contest

Moderate

0/80

Average time to solve is 25m

Contributed by

76 upvotes

Problem statement

School is organizing a team contest. You are given an array ‘SKILL’ containing the skill level of ‘N’ candidates.

Two candidates(having index ‘i’ and ‘j’) can pair up to form a team if for index i < j, SKILL[i] > 2*SKILL[j].

Your task is the return the count of all the possible pairs to take part in the contest.

Example:

Input: ‘N’ = 5
‘SKILL’ = [4, 1, 2, 3, 1] 

Output: 3
Explanation:
Possible pairs are (4,1), (4,1), (3,1).

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer, ‘N’, representing the number of candidates.

The next line contains ‘N’ space-separated integers, representing the skill level of N candidates.

Output format:

Return an integer, the count of all the possible pairs to participate in the contest.

Sample Input 1:

5
4 1 2 3 1

Sample Output 1 :

Explanation Of Sample Input 1:

Possible pairs are (4,1), (4,1), and (3,1).

Sample Input 2:

4 
100 49 201 100

Sample Output 2 :

Constraints:

1  <= N <= 10^5
1 <= SKILL[i] <= 10^6
Time Limit: 1 sec

Hint 1

Divide and Conquer.

Approaches (1)

Approach 1

Merge Sort

Approach:

The solution to the problem lies in writing a merge sort function and calling left and right recursion. We also need to write a merge function to count the total valid pairs in the left and right halves and then merge them using the temporary array.

The steps are as follows:

Function int merge([int] SKILL, int low, int high, int mid)

Assign total with 0.
Assign ‘idx’ with mid+1.
For loop ‘itr’ in range low to mid.
- Increase idx till idx <= high and SKILL[itr] > 2*SKILL[idx].
- Add idx-(mid+1) to total.
Create temporary array ‘temp’.
Assign left with low and right with mid+1.
While left <= mid and right <= high
- If SKILL at left <= SKILL at right
  - Push SKILL at left in temp, and increase left.
- Else
  - Push SKILL at right in temp, and increase right.
Push SKILL from left to midin temp.
Push SKILL from right to high in temp.
For loop ‘itr’ in the range low to high.
- Assign SKILL at itr with temp at (itr-low).
Return total.

Function int mergeSort([int] SKILL, int low, int high)

Return 0, if low is greater than equal to high.
Assign mid with (low + high)/2.
Assign count with the sum of mergeSort(SKILL, low, mid) and mergeSort(SKILL, mid+1, high).
Add merge(SKILL, low, high, mid) to count.
Return count.

Function int teams([int] SKILL, int N)

Return mergeSort(SKILL, 0, N-1).

Time Complexity

O( N * log(N) ), Where N is the length of the array.

Dividing takes log(N) operations, merging takes N operations and counting takes N operations.

Hence the time complexity is O( N * log(N) ).

Space Complexity

O( N ), Where N is the length of the array.

As we are using a temporary array for merging operations.

Hence the space complexity is O( N ).

(100% EXP penalty)

Team Contest

Arav Kumar Prasad

Interview problems

C++ Solution || Team Contest

void merge(vector<int> &arr, int low, int mid, int high) {

vector<int> temp; // temporary array

int left = low; // starting index of left half of arr

int right = mid + 1; // starting index of right half of arr

//storing elements in the temporary array in a sorted manner//

while (left <= mid && right <= high) {

if (arr[left] <= arr[right]) {

temp.push_back(arr[left]);

left++;

}

else {

temp.push_back(arr[right]);

right++;

}

// if elements on the left half are still left //

while (left <= mid) {

temp.push_back(arr[left]);

left++;

}

// if elements on the right half are still left //

while (right <= high) {

temp.push_back(arr[right]);

right++;

}

// transfering all elements from temporary to arr //

for (int i = low; i <= high; i++) {

arr[i] = temp[i - low];

}

int countPairs(vector<int> &arr, int low, int mid, int high) {

int right = mid + 1;

int cnt = 0;

for (int i = low; i <= mid; i++) {

while (right <= high && arr[i] > 2 * arr[right]) right++;

cnt += (right - (mid + 1));

}

return cnt;

}

int mergeSort(vector<int> &arr, int low, int high) {

int cnt = 0;

if (low >= high) return cnt;

int mid = (low + high) / 2 ;

cnt += mergeSort(arr, low, mid); // left half

cnt += mergeSort(arr, mid + 1, high); // right half

cnt += countPairs(arr, low, mid, high); //Modification

merge(arr, low, mid, high); // merging sorted halves

return cnt;

}

int team(vector <int> & skill, int n)

{

return mergeSort(skill, 0, n - 1);

}

69 views

0 replies

0 upvotes

MENAKA A

Interview problems

reversePairs - java optimal approach using merge sort Time complexity:O(2NlogN) Space complexity: O(N) for extra usage of arraylist

import java.util.ArrayList;

public class Solution {

private static void merge(int[] arr, int low, int mid, int high) {

ArrayList<Integer> temp = new ArrayList<>(); // temporary array

int left = low; // starting index of left half of arr

int right = mid + 1; // starting index of right half of arr

//storing elements in the temporary array in a sorted manner//

while (left <= mid && right <= high) {

if (arr[left] <= arr[right]) {

temp.add(arr[left]);

left++;

} else {

temp.add(arr[right]);

right++;

}

// if elements on the left half are still left //

while (left <= mid) {

temp.add(arr[left]);

left++;

}

// if elements on the right half are still left //

while (right <= high) {

temp.add(arr[right]);

right++;

}

// transfering all elements from temporary to arr //

for (int i = low; i <= high; i++) {

arr[i] = temp.get(i - low);

}

public static int countPairs(int[] arr, int low, int mid, int high) {

int right = mid + 1;

int cnt = 0;

for (int i = low; i <= mid; i++) {

while (right <= high && arr[i] > 2 * arr[right]) right++;

cnt += (right - (mid + 1));

}

return cnt;

}

public static int mergeSort(int[] arr, int low, int high) {

int cnt = 0;

if (low >= high) return cnt;

int mid = (low + high) / 2 ;

cnt += mergeSort(arr, low, mid); // left half

cnt += mergeSort(arr, mid + 1, high); // right half

cnt += countPairs(arr, low, mid, high); //Modification

merge(arr, low, mid, high); // merging sorted halves

return cnt;

}

public static int team(int []skill, int n){

// Write your code here.

int cnt = mergeSort(skill,0,n-1);

return cnt;

}

55 views

0 replies

1 upvote

Karthikeyan M

Interview problems

Python Easy Solution - Beats 96%

from sortedcontainers import SortedList

def team(skill: [int], n: int) -> int:

# Write your code here.

#return mergeSort(skill, 0, n-1)

ans = 0

sl = SortedList()

for i in range(n):

ans += sl.bisect_left(-(skill[i] * 2))

sl.add(-skill[i])

return ans

pass

python

49 views

0 replies

0 upvotes

Deepak

Interview problems

Count Reverse Pairs with merge sort

public class Solution {

public static int team(int []skill, int n){

return merge(skill, 0, skill.length-1);

}

public static int merge(int [] array , int start , int end ){

if(start >= end){

return 0;

}

int count = 0 ;

int medium = (start + end)/2;

count+= merge(array, start, medium);

count+= merge(array, medium+1, end);

count+= mergerr(array, start, medium, end);

return count ;

}

public static int mergerr(int[] array , int start , int mid , int end){

int count = 0 ;

int [] temparray = new int[end-start + 1];

int left = start ;

int right = mid+1;

int te = 0;

while(left <= mid && right <= end){

if(array[left] > 2 * array[right]){

count+= (mid - left) + 1;

right++;

} else {

left++;

}

left = start ;

right = mid+1;

te = 0;

while(left <= mid && right <= end){

if(array[left] < array[right]){

temparray[te] = array[left];

te++;

left++;

} else {

temparray[te] = array[right];

te++;

right++;

}

while(left <= mid){

temparray[te] = array[left];

te++;

left++;

}

while(right <= end){

temparray[te] = array[right];

te++;

right++;

}

for(int i = 0 , j = start ; i < temparray.length; i++ , j++){

array[j] = temparray[i];

}

return count ;

}

239 views

0 replies

0 upvotes

Ajeet Kumar

Interview problems

PYTHON

def merge(arr, low, mid, high):

temp = []

left = low

right = mid + 1

while left <= mid and right <= high:

if arr[left] <= arr[right]:

temp.append(arr[left])

left += 1

else:

temp.append(arr[right])

right += 1

while left <= mid:

temp.append(arr[left])

left += 1

while right <= high:

temp.append(arr[right])

right += 1

for i in range(low, high + 1):

arr[i] = temp[i - low]

def countPairs(arr, low, mid, high):

right = mid + 1

cnt = 0

for i in range(low, mid + 1):

while right <= high and arr[i] > 2 * arr[right]:

right += 1

cnt += (right - (mid + 1))

return cnt

def mergeSort(arr, low, high):

cnt = 0

if low >= high:

return cnt

mid = (low + high) // 2

cnt += mergeSort(arr, low, mid)

cnt += mergeSort(arr, mid + 1, high)

cnt += countPairs(arr, low, mid, high)

merge(arr, low, mid, high)

return cnt

def team(skill: [int], n: int) -> int:

return mergeSort(skill, 0, n - 1)

50 views

0 replies

0 upvotes

Satyasarat

Interview problems

Can anyone pls explain why this code does not produce correct results?

public class Solution {

public static int merge(int[] skill, int low, int mid, int high)

{

int count=0;

int m=mid-low+1;

int n=high-mid;

int[] first=new int[m];

int[] second=new int[n];

for(int i=0;i<m;i++)

{

first[i]=skill[low+i];

}

for(int i=0;i<n;i++)

{

second[i]=skill[mid+1+i];

}

int x=0,y=0,z=low;

while(x<m && y<n)

{

if(first[x]<=second[y])

{

skill[z]=first[x];

x++;

}

else

{

if(first[x]>(2*second[y]))

{

count+=(m-x);

}

skill[z]=second[y];

y++;

}

z++;

}

while(x<m)

{

skill[z]=first[x];

z++;

x++;

}

while(y<n)

{

skill[z]=second[y];

z++;

y++;

}

return count;

}

public static int mergeSort(int[] skill,int low,int high)

{

int count=0;

if(low<high)

{

int mid=(low+high)/2;

count+=mergeSort(skill,low,mid);

count+=mergeSort(skill,mid+1,high);

count+=merge(skill,low,mid,high);

}

return count;

}

public static int team(int []skill, int n){

return mergeSort(skill,0,n-1);

}

java

76 views

0 replies

0 upvotes

Rohan Sunwar

Interview problems

easy msort implementation

void merge( vector<int> &arr, int low, int mid, int high)

{

vector<int> temp;

int left = low;

int right = mid + 1;

while (left <= mid && right <= high)

{

if (arr[left] < arr[right])

{

temp.push_back(arr[left]);

left++;

}

else

{

temp.push_back(arr[right]);

right++;

}

while (left <= mid)

{

temp.push_back(arr[left]);

left++;

}

while (right <= high)

{

temp.push_back(arr[right]);

right++;

}

for (int i = low; i <= high; i++)

{

arr[i] = temp[i - low];

}

int countPair(vector<int> &arr, int low, int mid, int high){

int right = mid+1;

int cnt= 0;

for( int i = low; i<= mid;i++){

while(right <= high && arr[i] > 2 * arr[right]) right++;

cnt += (right - (mid+1));

}

return cnt;

}

int ms(vector<int> &arr, int low, int high){

int cnt =0;

if(low >= high) return cnt;

int mid = (low + high) /2;

cnt += ms(arr, low, mid);

cnt += ms(arr, mid+1, high);

cnt += countPair(arr, low, mid, high);

merge(arr, low, mid, high);

return cnt;

}

int team(vector <int> & skill, int n)

{

// Write your code here.

return ms(skill, 0, n-1);

}

255 views

0 replies

0 upvotes

TANIRU KAVYA SRI

Interview problems

****Optimal Code********************

Intuition The problem requires counting the number of reverse pairs in an array, where a reverse pair is defined as a pair of indices (i, j) such that i < j and nums[i] > 2 * nums[j]. Approach We can use the merge sort algorithm to efficiently count the number of reverse pairs. During the merge step of the merge sort, whenever we find a pair of elements (nums[i], nums[j]) such that nums[i] > 2 * nums[j], we increment the count of reverse pairs by the number of elements remaining in the left subarray (mid - i + 1). Complexity Time complexity: O(n log n) - The time complexity of merge sort. Space complexity: O(n) - Additional space required for the merge sort algorithm.

#include <bits/stdc++.h>

using namespace std;

void merge(vector<int> &arr, int low, int mid, int high) {

vector<int> temp; // temporary array

int left = low; // starting index of left half of arr

int right = mid + 1; // starting index of right half of arr

//storing elements in the temporary array in a sorted manner//

while (left <= mid && right <= high) {

if (arr[left] <= arr[right]) {

temp.push_back(arr[left]);

left++;

}

else {

temp.push_back(arr[right]);

right++;

}

// if elements on the left half are still left //

while (left <= mid) {

temp.push_back(arr[left]);

left++;

}

// if elements on the right half are still left //

while (right <= high) {

temp.push_back(arr[right]);

right++;

}

// transfering all elements from temporary to arr //

for (int i = low; i <= high; i++) {

arr[i] = temp[i - low];

}

int countPairs(vector<int> &arr, int low, int mid, int high) {

int right = mid + 1;

int cnt = 0;

for (int i = low; i <= mid; i++) {

while (right <= high && arr[i] > 2 * arr[right]) right++;

cnt += (right - (mid + 1));

}

return cnt;

}

int mergeSort(vector<int> &arr, int low, int high) {

int cnt = 0;

if (low >= high) return cnt;

int mid = (low + high) / 2 ;

cnt += mergeSort(arr, low, mid); // left half

cnt += mergeSort(arr, mid + 1, high); // right half

cnt += countPairs(arr, low, mid, high); //Modification

merge(arr, low, mid, high); // merging sorted halves

return cnt;

}

int team(vector <int> & skill, int n)

{

return mergeSort(skill, 0, n - 1);

}

208 views

0 replies

0 upvotes

JEYA KRISHNAN R

Interview problems

This is my code .while i submit it .It has an error Time limit exceeded even it pass all test case

int cnt=0;

int i=0,j=i+1;

while(i<n-1){

if(skill[i]>2*skill[j]){

cnt++;

}

if(j>=n-1){

i++;

j=i+1;

}else{

j++;

}

return cnt;

159 views

2 replies

0 upvotes

Abhishek Singh

Interview problems

JavaSolution | Optimised

import java.util.ArrayList;

public class Solution {

public static void merge(int []arr, int low, int mid, int high){

ArrayList<Integer> temp = new ArrayList<>();

int left = low;

int right = mid+1;

while(left<= mid && right<= high){

if(arr[left]<=arr[right]){

temp.add(arr[left]);

left++;

}else{

temp.add(arr[right]);

right++;

}

while(left<=mid){

temp.add(arr[left]);

left++;

}

while(right<= high){

temp.add(arr[right]);

right++;

}

for(int i = low; i<=high;i++){

arr[i] = temp.get(i-low);

}

public static int countPairs(int[] arr, int low, int mid, int high) {

int right = mid + 1;

int count = 0;

for (int i = low; i <= mid; i++) {

while (right <= high && arr[i] > 2 * arr[right]) {

right++;

}

count += (right - (mid + 1));

}

return count;

}

public static int mergeSort(int[] arr, int low, int high) {

int cnt = 0;

// Base case

if (low >= high)

return cnt;

int mid = low + (high - low) / 2;

// Conditiion

cnt += mergeSort(arr, low, mid);

cnt += mergeSort(arr, mid + 1, high);

cnt += countPairs(arr, low, mid, high);

merge(arr, low, mid, high);

return cnt;

}

public static int team(int[] skill, int n) {

// Write your code here.

return mergeSort(skill, 0, n - 1);

}

166 views

0 replies

0 upvotes

Console