Coding

Maximum Consecutive Good Numbers

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array of integers nums and an array goodNumbers, return the **maximum **number of **consecutive **good numbers in the array.

Any number present in the **goodNumbers **array is a good number.

Input: nums = [1, 2, 3, 5, 4, 5, 1], goodNumbers = [3, 5] Output: 2 Explanation: [1, 2, 3, 5, 4, 5, 1] the underlined numbers are all good numbers and give the maximum length.

Input: nums = [4, 8, 1, 2, 0, 4, 6], goodNumbers = [1, 4, 2, 6] Output: 2 Explanation: [4, 8, 1, 2, 0, 4, 6] the underlined numbers are all good numbers and give the maximum length. Note that the segment with index** [5, 6]** (0 - Based) was also a possible answer.

1 <= nums.length <= 105
1 <= goodNumbers.length <= 105
-104 <= nums[i], goodNumbers[i] <= 104

cpp

class Solution {
public:
    int maxConsecutiveGoodNums(vector<int>& nums, vector<int>& goodNumbers) {

    }
};

java

class Solution {
    public int maxConsecutiveGoodNums(int[] nums, int[] goodNumbers) {
        
    }
}

python

class Solution:
    def maxConsecutiveGoodNums(self, nums, goodNumbers):

javascript

class Solution {
    maxConsecutiveGoodNums(nums, goodNumbers) {

    }
}

csharp

public class Solution {
    public int MaxConsecutiveGoodNums(List<int> nums, List<int> goodNumbers) {

    }
}

func maxConsecutiveGoodNums(nums []int, goodNumbers []int) int {

}

Stuck? Show a way to structure it+

01Put good numbers in a hash set.
02Scan nums once.
03Increment a current run for good values and reset otherwise.
04Track the largest current run.

Reference answer

Convert goodNumbers to a hash set, then scan nums. If a number is in the set, increment current; otherwise reset it to zero. Maximize best after every increment. This is O(n+g) expected time and O(g) space, where g is the number of good values. A nested scan of every run is unnecessary, and duplicates in goodNumbers do not affect membership. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

How would you return the run boundaries?
Tests: index tracking
How would dynamic updates to goodNumbers change the design?
Tests: data structures

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question