Destroy Sequential Targets

Medium
859.

Destroy Sequential Targets

Destroy Sequential Targets is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google, Intuit and Dream11 interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} space
 * @return {number}
 */
var destroyTargets = function(nums, space) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Destroy Sequential Targets

  1. Hint 1

    A target at position p is destroyed by seed s exactly when p >= s and p ≡ s (mod space).

  2. Hint 2

    Since the seed must itself be one of the positions, the seed with residue r that destroys the most is the smallest position with residue r.

  3. 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

  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

Java

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