Katkat
Back

Maximal Square and Longest Increasing Subsequence

SalesforceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests proficiency with 2D dynamic programming for geometric pattern recognition and 1D dynamic programming for sequence optimization.

Part 1: Maximal Square

Given a 2D matrix of size m x n filled with '0's and '1's, find the area of the largest square containing only '1's.

Function Signature

def maximalSquare(matrix: List[List[str]]) -> int:

Example

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4 (The largest square is 2x2)

Part 2: Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Function Signature

def lengthOfLIS(nums: List[int]) -> int:

Example

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18] Output: 4 (The subsequence is [2, 3, 7, 101])

Constraints

  • matrix dimensions: up to 300x300.
  • nums length: up to 2500.
  • For Part 2, attempt to achieve a time complexity better than O(n^2).

Edge Cases

  • Empty matrix or empty array.
  • Matrices containing only '0's.
  • Arrays with duplicate values or all identical values.

Hints

Hint 1

For the maximal square, use a DP table where `dp[i][j]` represents the side length of the square ending at `(i, j)`.

Hint 2

For LIS, consider maintaining a list where each element at index `i` is the smallest tail of all increasing subsequences of length `i+1`.

Hint 3

Binary search can be used within the LIS construction to efficiently find the insertion point for each element in the input array.

Follow-up questions

  • How would you modify the maximal square algorithm to handle a matrix that is too large to fit in memory if it were processed row-by-row?
  • If the LIS problem required returning the actual subsequence rather than just the length, how would you store the 'witness' pointers?
  • Compare the time and space complexity trade-offs between your current implementations and a potential recursive approach with memoization.