Count Islands from Streaming Rows
Updated
Problem statement
A binary matrix arrives one row at a time from top to bottom. Given those rows as the finite ordered batch rows, return an array where result i is the number of islands present after rows 0 through i have arrived.
An island is a maximal group of '1' cells connected horizontally or vertically. Process rows in order and use auxiliary state proportional to the row width rather than retaining the entire matrix.
Function
islandCountAfterEachRow(rows: String[]) → int[]Examples
Example 1
rows = ["110","010","011"]return = [1,1,1]Each new land cell joins the component that began in the first row.
Example 2
rows = ["101","111","001"]return = [2,1,1]The second row joins the two first-row islands into one component.
Example 3
rows = ["000","000"]return = [0,0]No prefix contains land.
Constraints
1 <= rows.length <= 100000.1 <= rows[i].length <= 1000, and every row has equal length.rows.length * rows[i].length <= 1000000.- Every character is
'0'or'1'. - The algorithm must use
O(rows[i].length)auxiliary memory.
More Amazon Onsite Interview questions
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Dungeon GameONSITE INTERVIEW · Seen Nov 2026
- Integer BreakONSITE INTERVIEW · Seen Nov 2026
- LFU CacheONSITE INTERVIEW · Seen Nov 2026
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
- First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Largest Island After One Land ConversionGoogle · ONSITE INTERVIEWGoogle interview questions
- Making a Large IslandMeta · ONSITE INTERVIEWMeta interview questions
- Explore an Unknown Grid and Find a PathLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Connected GroupsFivetran · ONSITE INTERVIEWFivetran interview questions
- Dynamic Island CountsUber · PHONE SCREENUber interview questions
- Number of Islands IISpaceX · PHONE SCREENSpaceX interview questions
- Biggest Connected ComponentCodeium · OACodeium interview questions
- Capture Surrounded Regions with Union-FindApple · PHONE SCREENApple interview questions
- Connected GroupsVisa · OAVisa interview questions
- Xiangqi Horse ReachabilityeBay · PHONE SCREENeBay interview questions
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences