1.
Introduction
2.
Problem Statement
2.1.
INPUT
2.2.
OUTPUT
2.3.
Explanation
2.4.
INPUT
2.5.
OUTPUT
2.6.
Explanation
2.7.
Constraints
3.
Solution
3.1.
Program
3.2.
INPUT
3.3.
OUTPUT
3.4.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Maximum Score Difference

0 upvote

## Introduction

In this blog, we'll look at a problem that involves arrays, sorting, and binary search. Array-based questions are the most popular in coding interviews and programming contests. Binary search is used to solve a variety of problems. This article will look at a situation that combines both of these ideas.

## Problem Statement

Given two arrays A and B. Find the score of A and B such that their difference is maximum.

The score is calculated in the following manner. For each element:

• +2 points if element < L
• +3 points if element >= L,

where L is some non-negative integer.

A = [1, 2, 3]

B = [5, 6]

9:6

### Explanation

Let L = 0.

As each element in the first array is greater than 0, total score = 3 + 3 + 3 = 9.

As each element in the second array is greater than 0, total score = 3 + 3 = 6.

You can check this is the maximum difference possible.

### INPUT

A = [3, 8, 5, 11]

B = [4, 8, 10]

12:9

### Explanation

Let L = 0.

As each element in the first array is greater than 0, total score = 3 + 3 + 3 + 3 = 12.

As each element in the second array is greater than 0, total score = 3 + 3 = 6.

You can check this is the maximum difference.

### Constraints

Let N, M be the length of arrays A and B respectively.

1 <= N, M <= 10^3

1 <= Ai, Bi <= 10^5

## Solution

Brute Force approach:

We can take values from 0 to max(array A) for L. After fixing the value of L, we simply calculate the scores of both arrays and find the maximum difference.

After iterating on all values of L, we can print the final scores.

Time complexity of this approach is O(|max(array A)| * |max(N, M)|). It is clear from the constraints that this approach is very inefficient.

Let us now look at efficient approaches to this problem.

Efficient approach:

We don’t need to check for every value in [0, max(array A)] as L. Instead, we take L as elements in array A.

For calculating the scores efficiently, we use binary search. Here 2 points are contributed for every element which is less than L and +3 for elements greater than equal to L. We sort both arrays.

For every element in A, where A[i] is set as L, we find scores of both the array.

For array A, elements before the current element will contribute +2, and elements after the current element will contribute +3.

For array B, we find the first index, greater than equal to L, and then similar to array A, elements after this index contributes +3 and elements before a +2 in the score.

After iterating over the whole array A, we print the final scores of A and B.

### Program

``````#include <bits/stdc++.h>
using namespace std;

void solve(){
int tt;
// number of test cases.
cin >> tt;
while(tt--){
// taking inputs.
int n;cin >> n;
vector<int>a(n+1);
for(int i=0; i<n; i++)cin >> a[i];
a[n++] = INT_MAX;

int m;cin >> m;
vector<int>b(m);
for(int i=0; i<m; i++)cin >> b[i];
// sort the arrays.
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// find the optimal L.
int p=0, q=0;
int diff = INT_MIN;
for(int i=0; i<n; i++){
int L = a[i];

int scoreA = 2*i + 3*(n-i-1);
int idxB = lower_bound(b.begin(), b.end(), L) - b.begin();
// int idxB = upper_bound(b.begin(), b.end(), L-1) - b.begin();
int scoreB = 2*idxB + 3*(m - idxB);
// update when you find a new optimal L.
if(scoreA-scoreB > diff){
// take account of the new optimal difference.
diff = scoreA -scoreB;
p = scoreA;
q = scoreB;
}
}
cout << p << ":" << q << endl;
}
}

int main(){
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
solve();
return 0;
}``````

### INPUT

``````2
3
1 2 3
2
5 6
5
6 7 8 9 10
5
1 2 3 4 5``````

### OUTPUT

``````9:6
15:10``````

Time Complexity

Sorting takes O(n*log(n)). Binary search is used when iterating over array A. The time complexity of lower_bound is O(log(m))

The overall time complexity of the program is O(N*(log(M) + log(N))).

### Space Complexity

The auxiliary space complexity of the program is O(1)

## FAQs

Q1). Explain the lower_bound() function in C++?

This function returns an iterator pointing to the first element in the container, which is greater than equal to the value.

Q2). Explain the upper_bound() function in C++?

This function returns an iterator pointing to the first element in the container, which is greater than the value.

Q3). What is the time complexity of lower_bound()upper_bound() functions in C++?

The time complexity of lower_bound & upper_bound is O(log(N)).

Q4). What is the underlying algorithm of sort() function in C++?

The sort() function uses IntroSort. IntroSort is a hybrid sorting technique that uses Quicksort, Heapsort, and Insertionsort to minimize the running time.

## Key Takeaways

Cheers if you reached here!!

The purpose of this article was to discuss an intriguing problem using arrays and sorting. Array-based problems are sometimes simple to implement, but finding an efficient approach remains a difficulty.

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!

Live masterclass