Wayfair
  • OA
    • Karat
      • 811. Subdomain Visit Count
      • Ads Conversion Rate
      • Recommend Movie
      • Longest Common Continuous Subarray
      • Course Overlap
      • Halfway courses
      • Find one rectangle
      • Find all rectangles
      • Find Multiple Shapes
      • word wrap
      • word processor
      • Basic Calculator
      • Basic Calculator with parenthesis
      • 带变量计算器
      • Valid Matrix
      • nonogram
      • Node with 0 or 1 parents
      • 两个节点是否有公共祖先
      • 最远祖先
      • invalid Badge Records
      • 一小时内access多次
      • canSchedule
      • spareTime
      • sparse vector
      • sparse vector 实现add,dot和cos
      • userlogs earliest and latest access time
      • resource Access with in 5 min
      • Find Word Path in Grid
      • Find legal moves
      • 找能去的所有0区域
      • 最短路径找treasure
  • VO
    • Coding
      • Valid Palindrome
      • Add String
      • Coupon
    • System design
    • BQ
    • OOD
  • SD
  • LeetCode Tag
  • VO Onsite
Powered by GitBook
On this page
  1. OA
  2. Karat

Find Multiple Shapes

the image has random shapes filled with 0s, separated by 1s. Find all the shapes. Each shape is represented by coordinates of all the elements inside.

Similar as LC 200

public class Main {
    public List<List<Integer>> findMultipleShapes(int[][] board)
    {
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0; i< board.length; i++)
        {
            for(int j = 0; j< board[0].length; j++)
            {
                if(board[i][j] == 0)
                {
                    List<Integer> shape = new ArrayList<Integer>();
                    dfs(board, i, j, shape);
                    result.add(shape);
                }
            }
        }
        return result;
    }

    public void dfs(int[][] board, int x, int y, List<Integer> shape)
    {
        if(!isBound(board, x, y))
        {
            return;
        }
        if(board[x][y] == 1)
        {
            return;
        }
        shape.add(x);
        shape.add(y);
        board[x][y] = 1;

        dfs(board, x-1, y, shape);
        dfs(board, x+1, y, shape);
        dfs(board, x, y-1, shape);
        dfs(board, x, y+1, shape);
    }

    public boolean isBound(int[][] board, int x, int y)
    {
        return x>=0 && x<board.length && y>=0 && y<board[0].length;
    }
}

PreviousFind all rectanglesNextword wrap

Last updated 3 years ago