Fresh Oranges Left After Rotting Stops
Updated
Problem statement
You are given an m x n grid. Each cell holds one of three values:
0: an empty cell,1: a fresh orange,2: a rotten orange.
Every minute, each fresh orange that shares a side (up, down, left or right) with a rotten orange becomes rotten. Rot does not pass through empty cells, does not move diagonally, and does not wrap around the edges of the grid. This goes on until a minute passes in which no new orange rots.
Return the number of oranges that are still fresh when the rotting stops.
Function
freshOrangesLeft(grid: int[][]) → intExamples
Example 1
grid = [[2,1,0,1],[1,1,0,1],[0,1,1,0]]return = 2The rotten orange at the top left rots its neighbors one minute at a time: first (0, 1) and (1, 0), then (1, 1), then (2, 1), then (2, 2). The two fresh oranges in the last column, (0, 3) and (1, 3), are cut off by empty cells, so rot never reaches them. The answer is 2.
Example 2
grid = [[1,1,1],[1,2,1],[1,1,1]]return = 0After one minute, the four oranges that share a side with the center have rotted. After the second minute, the four corners have rotted too. No fresh orange is left, so the answer is 0.
Example 3
grid = [[2,0,1],[0,1,1]]return = 3The rotten orange at (0, 0) has only empty cells beside it. The orange at (1, 1) touches it only at a corner, and corners do not count. Nothing ever rots, so all 3 fresh oranges are left.
Constraints
1 <= grid.length <= 1001 <= grid[i].length <= 100- All rows of
gridhave the same length. grid[i][j]is0,1or2.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
- Maximum Supplier ProfitONSITE INTERVIEW · Seen Aug 2024
Similar questions at other companies
- Rotting OrangesSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Minimum Time to Spread Through a GridAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Minimum Time to Rot All OrangesMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Shortest Increasing Path to a TargetUber · ONSITE INTERVIEWUber interview questions
- Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Rotting OrangesOtter.ai · ONSITE INTERVIEWOtter.ai interview questions
- Fuel-Aware Grid ReachabilityBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Number of Fish in a GridGlobalization Partners · ONSITE INTERVIEW
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)