📖
Coding problems
  • Overview
  • Second time
  • Third time
  • 2 sum
    • 2 sum?
    • 2 Sum All Pair I
    • 2 Sum All Pair II
    • 3 Sum
  • Array
    • Smallest and Largest
    • Largest and second largest
    • Longest Palindromic Substring
  • BFS
    • Array Hopper IV
    • Deep copy graph(possible loops)
    • Kth Smallest With Only 3, 5, 7 As Factors
    • Word Ladder
  • Binary Search
    • Closest in Sorted Array
    • Smallest Element that is larger than target
    • Search in unknown size array
  • Bit Operations
    • Basic Operations
    • Power of two?
    • Different bits
    • Reverse all bits of a number
    • Unique String
  • Deque
    • Deque with 3 stacks
    • Largest Rectangle in histogram
  • DFS Permutations
    • All subsets I
    • All subsets size k
    • Combinations For Telephone Pad I
    • Subsets of all permuations
    • Generate N valid parentheses I
    • Generate N valid parentheses II
    • Generate N valid parentheses III
    • Combinations of Coin
    • All Permutation String
    • All Permutations II
    • Telephone Combinations
  • Dynamic Programming
    • Array Hopper I
    • Array Hopper II
    • Array Hopper III
    • Cut Rope
    • Dictionary Word 1
    • Dictionary Word II
    • Eat Pizza
    • Largest Cross of Ones
    • Largest Square Surrounded By One
    • Largest X of 1s
    • Largest Square of Matches
    • Largest Submatrix Sum
    • Longest Ascending Subsequence I & II
    • Longest Common Sequence between two strings
    • Most with positive slope
    • Palindrome Partition
    • Edit Distance
    • Square of ones
    • Wild card matching
    • Wood Cutting
    • 188. Best Time to Buy and Sell Stock IV
  • Graph Search
    • Kth closest to <0, 0, 0>
    • Largest Product of Length
  • HashTable
    • Top K frequent words
    • Bipartite
  • Heap
  • LinkedList
    • Reverse
    • Merge Sort Linked List
    • Re-Order LinkedList
  • Slow fast pointers
    • Remove duplicate elements in array
  • Problem Solving
    • Water Level I
    • Largest rectangle in histogram
    • Range Addition II
  • Recursion
    • ReverseTree
    • NQueen
    • NQueen optimized
    • Spiral Order Print I
    • Spiral Order Print II
    • String Abbreviation Matching
  • Sliding Window
    • Longest subarray contains only 1s
    • Longest Substring Without Repeating Characters
    • Maximum Number within Window
  • Sorts
    • QuickSort
  • String
    • All Anagrams
    • is substring of string
    • Reverse String
    • Reverse Words on sentence
    • Remove Chars from String in place
    • Right shift N characters
    • Remove Leading/duplicate/trailing spaces
    • Shuffle String
    • String Abbreviation Matching
  • Tree Traversal
    • Check balanced tree
    • Check if complete tree
    • Delete in binary tree
    • LCA of two tree nodes
    • Get Keys In Binary Search Tree In Given Range
    • Height of Tree
    • Symmetric Tree?
    • Tweaked Binary tree
    • Set left node count
    • Greatest difference Left and Right subtree count Node
    • Largest Number Smaller in BST
    • Closest Number in Binary Search Tree II
    • Max Path Sum From Leaf To Root
    • Maximum Path Sum Binary Tree I
    • Maximum Path Sum Binary Tree II
    • Maximum Path Sum Binary Tree III
    • Flatten Binary Tree to Linked List
    • Iterative Post-Order Traversal
  • Unsorted Array
    • Find missing number
Powered by GitBook
On this page

Was this helpful?

  1. Dynamic Programming

Largest Cross of Ones

Given a matrix that contains only 1s and 0s, find the largest cross which contains only 1s, with the same arm lengths and the four arms joining at the central point.

Return the arm length of the largest cross.

Assumptions

  • The given matrix is not null, has size of N * M, N >= 0 and M >= 0.

Examples

{ {0, 0, 0, 0},

{1, 1, 1, 1},

{0, 1, 1, 1},

{1, 0, 1, 1} }

the largest cross of 1s has arm length 2.

public class Solution {
  public int largest(int[][] matrix) {
    int N = matrix.length;
    if (N == 0){
      return 0;
    }
    int M = matrix[0].length;
    if (M == 0) return 0;

    int[][] leftUp = leftUp(matrix, N, M);
    int[][] rightDown = rightDown(matrix,N,M);
    
    return merge(leftUp, rightDown, N, M);
  }

  private int merge(int[][] leftUp, int[][] rightDown, int N, int M){
    int result = 0;
    for (int i = 0; i < N; i++){
      for (int j =0; j < M; j++){
        leftUp[i][j] = Math.min(leftUp[i][j], rightDown[i][j]);
        result = Math.max(result, leftUp[i][j]);
      }
    }
    return result;
  }

  private int[][] leftUp(int[][] matrix, int N, int M){
    int[][] left = new int[N][M];
    int[][] up = new int[N][M];
    for (int i = 0; i < N; i++){
      for (int j = 0; j < M; j++){
        if (matrix[i][j] == 1){
          if (i == 0 && j == 0){
            up[i][j] = 1;
            left[i][j] = 1;
          } else if (i == 0){
            up[i][j] = 1;
            left[i][j] = left[i][j - 1] + 1;
          } else if (j == 0){
            up[i][j] = up[i - 1][j] + 1;
            left[i][j] = 1;
          } else {
            up[i][j] = up[i - 1][j] + 1;
            left[i][j] = left[i][j - 1] + 1;
          }
        }
      }
    }
    merge(left, up, N, M);
    return left;
  }

  private int[][] rightDown(int[][] matrix, int N, int M){
    int[][] right = new int[N][M];
    int[][] down = new int[N][M];
    for (int i = N - 1; i >= 0; i--){
      for (int j = M - 1; j >= 0; j--){
        if (matrix[i][j] == 1){
          if (i == N - 1 && j == M - 1){
            down[i][j] = 1;
            right[i][j] = 1;
          } else if (i == N - 1){
            down[i][j] = 1;
            right[i][j] = right[i][j + 1] + 1;
          } else if (j == M - 1){
            down[i][j] = down[i + 1][j] + 1;
            right[i][j] = 1;
          }  else{
            down[i][j] = down[i + 1][j] + 1;
            right[i][j] = right[i][j + 1] + 1;
          }
        }
      }
    }
    merge(right, down, N, M);
    return right;
  }
}

TC: O(NM) whole N x M 4 times

SC: O(NM) two N x M int[][] leftup and rightdown

PreviousEat PizzaNextLargest Square Surrounded By One

Last updated 4 years ago

Was this helpful?