Count Quadruples Summing to Target
Medium About 20 min Free, no account needed
Count index quadruples that sum to a target - without the quadruple loop.
The brief
Given an integer array nums and a target, count the number of index
quadruples i < j < k < l with
nums[i] + nums[j] + nums[k] + nums[l] == target.
The obvious approach enumerates every quadruple, O(n^4). The hidden test uses just 500 elements, but that is already 2.6 billion quadruples, far too slow. You will need an approach closer to O(n2).
Starter code
using System;
public class Solution
{
// TODO: return the count of quadruples i < j < k < l whose values sum to target.
public long CountFourSum(int[] nums, int target)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Do these first
Related katas
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Degree of an Array Medium Free Find the shortest contiguous slice whose most-frequent-element count matches the whole array.
- Find All Anagram Start Indices Medium Free Every position where an anagram of the pattern begins.
- Longest Consecutive Sequence Medium Free Find the length of the longest run of consecutive integers hiding in an unsorted array.