#2 pointers

Solutions A simple solution consists in running two nested for loops to calculate the possible costs. Although this solution is \(O(n \cdot m)\), it’s acceptable since the input is small: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int s, n, m; cin >> s >> n >> m; vector<int> k(n); copy_n(istream_iterator<int>(cin), n, begin(k)); vector<int> u(m); copy_n(istream_iterator<int>(cin), m, begin(u)); auto cost = -1; for(auto i : k) { for (auto j : u) { if (i+j<=s) cost = max(cost, i+j); } } cout << cost; Linq-based solution, with cartesian product (by fabrizio_sanmar1): [Read More]

You are given a sequence of integers S, your task is to find a pair i,j of indices with i<j that maximizes the difference S[j]-S[i]. Note that what makes this challenge more interesting is the requirement of order, that i < j (without it you simply need to find the maximum and minimum element of S). You have to output the value of the maximum difference. Input Format An integer N followed by N space separated integers S[i] on a new line. [Read More]

Solutions The brute force approach is easy: just run two nested loops and for each value \( x \) find if it exists a value equals to \( target - x \). This solution is quadratic. Efficient solutions are based either on sorting or additional storage (e.g. frequency table, hash maps). A sort-based solution Suppose we sort the prices \( p \) in ascending order. Consider the sum \( p[0] + p[n-1] \) where \( n \) is the number of available prices. [Read More]

Solutions A brute-force approach consists in enumerating all possible combination of pairs and check if any contains all pairs with the same sum. Enumerating and checking all the combinations is clearly expensive. Actually, there is only one possible combination that would satisfy the constraint and can be found directly. Intuitively, suppose we are 4 people and we want to play together in pairs. To make the match balanced, we have to join the strongest with the weakest. [Read More]

Warning: HackerRank has recently changed the constraints of this problem but it did not update the challenge itself. Now they allow zeros to be part of the input. In particular this can cause empty sub-arrays to be a valid solution. For example this was not valid input before the update: 1 2 0 0 0 Now it is. A solution is the position 0 since the left sub-array is empty. [Read More]

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order, in linear time. Input Format The first line contains N, the length of the array. The second line contains N space-separated integers, the elements of the array. Constraints \(1 \leq N \leq 10^6\) \(-10^3 \leq A[i] \leq 10^3\) Output Format Print the array of the squares of each number, also in sorted non-decreasing order. [Read More]