Destroy Sequential Targets — Medium Problem & Solution

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 <= 100000
• 1 <= nums[i] <= 1000000000
• 1 <= space <= 1000000000

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

1. Tally how many positions fall in each residue class modulo space.
2. 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium