Destroy Sequential Targets — Solution in Python, Java & C++
Destroy Sequential Targets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Destroy Sequential Targets is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google, Intuit and Dream11 interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Counting
- Asked at: Amazon, Google, Intuit, Dream11
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums[i] is the position of a target on a number line. Your machine is seeded with one of those positions seed and then destroys every target at seed, seed + space, seed + 2·space, and so on.
Return the seed that destroys the most targets. If several do, return the smallest such seed.
Example 1
Input: nums = [3,7,8,1,1,5], space = 2
Output: 1
Explanation: Seeding at 1 destroys 1, 1, 3, 5 and 7 — five targets — and 1 is the smallest seed achieving that.
Example 2
Input: nums = [1,3,5,2,4,6], space = 2
Output: 1
Explanation: Seeds 1, 3 and 5 all destroy three targets; 1 is smallest.
Example 3
Input: nums = [6,2,5], space = 100
Output: 2
Explanation: Each seed destroys only itself, so the smallest position wins.
Constraints
1 <= nums.length <= 1000001 <= nums[i] <= 10000000001 <= space <= 1000000000
Hints for Destroy Sequential Targets
Hint 1
A target at position
pis destroyed by seedsexactly whenp >= sandp ≡ s (mod space).Hint 2
Since the seed must itself be one of the positions, the seed with residue
rthat destroys the most is the smallest position with residuer.Hint 3
So group positions by residue, and the group size is the number destroyed.
How to solve Destroy Sequential Targets
Seeding at the smallest position of a residue class destroys every position in that class, because they are all at or above it and congruent. So the count for a seed is just its residue class's size, and the tie-break picks the smallest position.
Approach
- Tally how many positions fall in each residue class modulo
space. - Scan the positions, keeping the one whose class is largest; on a tie keep the smaller position.
Why it works
Every position congruent to the seed and at least as large is destroyed, and a position smaller than the seed is not — but since the tie-break already drives the answer towards the smallest position in its class, the seed that wins is the class minimum, which reaches all of them. That makes the class size the exact count for the winning seed.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The seed must be one of the given positions, not an arbitrary number.
- The tie-break is on the seed value, not on the index.
- Positions below the seed in the same class are not destroyed, which is why the class minimum is the right representative.
Reference solution
Python
from typing import List
def destroyTargets(nums: List[int], space: int) -> int:
cnt = {}
for x in nums:
r = x % space
cnt[r] = cnt.get(r, 0) + 1
best, ans = -1, 0
for x in nums:
c = cnt[x % space]
if c > best or (c == best and x < ans):
best, ans = c, x
return ansJava
public static int destroyTargets(int[] nums, int space) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) cnt.merge(x % space, 1, Integer::sum);
int best = -1, ans = 0;
for (int x : nums) {
int c = cnt.get(x % space);
if (c > best || (c == best && x < ans)) {
best = c;
ans = x;
}
}
return ans;
}C++
int destroyTargets(vector<int>& nums, int space) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x % space]++;
int best = -1, ans = 0;
for (int x : nums) {
int c = cnt[x % space];
if (c > best || (c == best && x < ans)) {
best = c;
ans = x;
}
}
return ans;
}JavaScript
var destroyTargets = function(nums, space) {
var cnt = {}, i;
for (i = 0; i < nums.length; i++) {
var r = nums[i] % space;
cnt[r] = (cnt[r] || 0) + 1;
}
var best = -1, ans = 0;
for (i = 0; i < nums.length; i++) {
var c = cnt[nums[i] % space];
if (c > best || (c === best && nums[i] < ans)) { best = c; ans = nums[i]; }
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets