Skip to main content

Posts

Leetcode 85: Maximal Rectangle

  This is a classic extension of  84. Largest Rectangle in Histogram . 1. Problem Statement (Simple Explanation) You’re given a binary matrix matrix of size rows x cols filled with '0's and '1's. You must find the  area of the largest rectangle  containing only '1's and return that area. The rectangle must be axis-aligned. It can span multiple rows and columns. 2. Examples Example 1: Input: matrix = [   ["1","0","1","0","0"],   ["1","0","1","1","1"],   ["1","1","1","1","1"],   ["1","0","0","1","0"] ] Largest all-ones rectangle has area  6 : For example, from row 1 to row 2, columns 2 to 4 (0-based), i.e.: [   [1,1,1],   [1,1,1] ] Output: 6 Example 2: Input: [["0"]] No '1's → max area = 0. Output: 0 Example 3: Input: [["1"]] Single cel...

Chopsticks

Problem Summary You have N sticks, where the i-th stick has length L[i]. You want to form pairs of sticks to be used as chopsticks. Rules: A pair is  usable  if the absolute difference in lengths of the two sticks is  at most  D. Each stick can be used in  at most one  pair. Goal: Find the  maximum number of valid pairs  you can form. Input: First line: two integers N and D. Next N lines: one integer per line, L[i] — length of the i-th stick. Output: One integer: maximum number of usable chopstick pairs. Constraints: 1 <= N <= 10 5 0 <= D <= 10 9 1 <= L[i] <= 10 9 Examples Explanation Input: 5 2 1 3 3 9 4 Output: 2 Sticks lengths: [1, 3, 3, 9, 4], maximum allowed difference D = 2. The stick of length 9 is too far from all others (differences > 2), so it will remain unused. Remaining sticks: 1, 3, 3, 4. One possible optimal pairing: (1, 3)...