Fewest Days Until a Point Holds k Variants
Updated
Problem statement
Several virus variants spread over an endless grid of whole-number points. Variant i starts on day 0 at the point points[i] = [xi, yi]. Each day, every point that holds a variant passes it on to its four neighbours: up, down, left and right. So after d days, variant i is at every point (x, y) with |x - xi| + |y - yi| <= d.
Return the smallest number of days d after which some single point holds at least k different variants. Two variants may start at the same point, and then the answer can be 0.
Function
minDaysForK(points: int[][], k: int) → intExamples
Example 1
points = [[2,3],[6,1],[5,7]]k = 2return = 3The closest two starts are (2, 3) and (6, 1), 4 + 2 = 6 steps apart; the other two pairs are 7 steps apart. After 3 days both of the closest variants have reached (4, 2), which is 2 + 1 = 3 steps from each. After 2 days no point is within 2 steps of two starts, since that would put them at most 4 steps apart.
Example 2
points = [[2,3],[6,1],[5,7]]k = 3return = 4All three variants must meet. The point (5, 3) is 3 + 0 = 3, 1 + 2 = 3 and 0 + 4 = 4 steps from the three starts, so after 4 days all three have reached it. 3 days are not enough: the starts (6, 1) and (5, 7) are 1 + 6 = 7 steps apart, so no point is within 3 steps of both.
Example 3
points = [[0,0],[1,0]]k = 2return = 1The starts are next to each other, 1 step apart. They cannot meet halfway, because only whole points exist. After 1 day the first variant has reached (1, 0), where the second one started.
Constraints
2 <= points.length <= 50points[i].length == 2and0 <= xi, yi <= 10^82 <= k <= points.length
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Light Source Hits: Sample, Compare, and FitOpenAI · PHONE SCREENOpenAI interview questions
- Maximize Fish over Limited HoursByteDance · PHONE SCREENByteDance interview questions
- Median Across Sorted ArraysGoogle · PHONE SCREENGoogle interview questions
- Merge Collinear Point SegmentsApplied Intuition · PHONE SCREENApplied Intuition interview questions
- Maximum Profit in Job SchedulingAmazon · PHONE SCREEN
- Closest Pair of PointsCitadel · PHONE SCREENCitadel interview questions
- Maximum Visible DronesAnduril · PHONE SCREENAnduril interview questions
- Maximum Event Value with an Attendance LimitSnowflake · PHONE SCREENSnowflake interview questions
- Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions
- Three Points in a Semicircle: Monte Carlo EstimateSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
Interview reports that mention this question
Adobe interview experiences
- Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
- Adobe SWE Interviews, Level Unknown: 25 Experiences (Part 2 of 3)
- Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
- Adobe New Grad MTS Interview Questions: 7 Experiences
- Adobe ML/Research Intern Interviews: 12 Experiences (Part 4 of 4)