#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). Brute force solution 1 2 3 4 5 6 7 8 9 10 fn solve(m: usize, flavors: &[usize]) -> (usize, usize) { for (i, x) in flavors. [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]

Solutions There exist several approaches and solutions to this problem. Some are very intuitive, others require to rack one’s brain. This challenge is a variation of the “Equilibrium Index,” and since it’s available as Sherlock and Array on this website, we won’t revisit all the solutions discussed there. For instance, solutions based on the prefix sum pattern are not covered here but can also be applied to this problem. For completeness, we mention the brute force solution that consists in iterating through potential server values from 1 to \( n \). [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]

Solutions A brute force solution to this problem involves checking every possible pair of numbers in the array and calculating their product. To do this, we use two nested loops: the outer loop selects the first number, and the inner loop selects the second number, which comes after the first. For each pair, we compute the product and check if it exceeds the current maximum product found. This approach guarantees finding the pair with the highest product, but it is inefficient because it examines all pairs, resulting in a quadratic time complexity. [Read More]