LeetCode Weekly Contest 176

• Count Negative Numbers in a Sorted Matrix
• Product of the Last K Numbers
• Maximum Number of Events That Can Be Attended
• Construct Target Array With Multiple Sums

Count Negative Numbers in a Sorted Matrix

[Problem] [Code]

Essentially a Young Tableau problem. Start from the right top right cell. At each step, we can either remove a row or a column.

Time: \(O(m + n)\)

Extra space: \(O(1)\)

Product of the Last K Numbers

[Problem] [Code]

My solution is a bit uncommon…

Pay attention to the following statement

At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

This means the following:

• The answer is 0 if there is at least a zero among the \(k\) numbers.
• If there’s no zero, the # of distinct numbers that are greater than 1 cannot be more than \(\log_2(k)\), which is less than 32.

Therefore, we can store the numbers in a compacted manner and then compute the product by brute-force.

Time: \(O(1)\) for add, \(O(32)\) for product

Space: \(O(add)\)

Maximum Number of Events That Can Be Attended

[Problem] [Code]

Sweep time stamp $t$ for 0 to \(10^5\), for each \(t\), we would like to

1. identify all the events whose interval contain \(t\), and
2. attend the event with earliest ending time if any.

Step 2 is the greedy step. For correctness:

• One needs to show that it cannot be worse to take an event at \(t\) if there’s any candidate.
• One also needs to prove that it cannot be worse to take the event with earliest end time among all the feasible candidates.

For implementation:

• Step 1 can be done efficiently via a global sorting on event’s start time.
• Step 2 can be maintained using a heap or balanced BST.

Time: \(O(n \log n)\)

Space: \(O(n)\)

Construct Target Array With Multiple Sums

[Problem] [Code]

Find the largest number in the array, then there’s a unique way to compute its value of the previous stage. Keep doing so until

• all numbers are equal to 1 –> True
• any number becomes negative –> False

Use a SortedList / a Max-Heap for quick indexing.

Time: \(O(n \log n \log C)\), where $C$ is the largest element in the given list.

Space: \(O(n)\)