📖
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 Square of Matches

PreviousLargest X of 1sNextLargest Submatrix Sum

Last updated 4 years ago

Was this helpful?

Determine the largest square surrounded by a bunch of matches (each match is either horizontal or vertical), return the length of the largest square.

The input is a matrix of points. Each point has one of the following values:

0 - there is no match to its right or bottom.

1 - there is a match to its right.

2 - there is a match to its bottom.

3 - there is a match to its right, and a match to its bottom.

Assumptions

The given matrix is guaranteed to be of size M * N, where M, N >= 0

Examples

{{3, 1, 1, 3, 0, 1, 1, 0},

{2, 0, 0, 2, 0, 0, 0, 0},

{3, 1, 3, 0, 0, 0, 0, 0},

{2, 0, 2, 0, 0, 0, 0, 0},

{1, 1, 0, 0, 0, 0, 0, 0}}

This matrix represents the following bunch of matches:

The largest square has length of 2.

public class Solution {

  public int largestSquareOfMatches(int[][] matrix) {
    int N = matrix.length;
    int M = matrix[0].length;

    if (N == 0 || M == 0) return 0;
    int result = 0;

    int[][] down = new int[N + 1][M + 1];
    int[][] right = new int[N + 1][M + 1];
    for (int i = N - 1; i >= 0; i--){
      for (int j = M - 1; j >= 0; j--){
        int curNum = matrix[i][j];
        if(hasRight(curNum)){
          right[i][j] = right[i][j + 1] + 1;
        }

        if(hasDown(curNum)){
          down[i][j] = down[i + 1][j] + 1;
        }

        //if has both, can make possible square
        if(hasBoth(curNum)){
          for(int maxLength = Math.min(down[i][j], right[i][j]); maxLength >= 1; maxLength--){
            //if two other edges exist at cur side length aka maxLength
            if(right[i + maxLength][j] >= maxLength && down[i][j + maxLength] >= maxLength){
              result = Math.max(result, maxLength);
            }
          }
        }
      }
    }
    return result;
    
  }

  private boolean hasRight(int num){
    if (num == 3 || num == 1) return true;
    return false;
  }

  private boolean hasDown(int num){
    if (num == 2 || num == 3) return true;
    return false;
  }

  private boolean hasBoth(int num){
    if (num == 3) return true;
    return false;
  }
}

TC: O(NM)

SC: O(NM)