- 1380. Lucky Numbers in a Matrix
- 1381. Design a Stack With Increment Operation
- 1382. Balance a Binary Search Tree
- 1383. Maximum Performance of a Team
1380. Lucky Numbers in a Matrix
Since all elements are distinct in the matrix, we can pre-compute the min value per each row and the max value per each column. Then, we scan the matrix one more time and find all the candidates.
Time: O(mn)
Space: O(m + n)
1381. Design a Stack With Increment Operation
Maintain each prefix increment pointwisely and lazily. Then all operations can be implemented in O(1) time.
1382. Balance a Binary Search Tree
Do an in-order traversal to obtain all the elements in BST in sorted order. Then build the balanced tree using Divide-and-Conquer.
Time: O(n)
Space: O(n)
1383. Maximum Performance of a Team
Enumerate the engineer that has the minimum efficiency in the team. When each engineer is fixed, find those (at most) k engineers that have top speed. This algorithm can be implemented efficiently by (i) a pre-sorting on efficiency in decreasing order and (ii) using a heap or BST to maintain top-k speed.
Time: O(n log n + n log k) = O(n log n)
Space: O(k + sorting). When using (say) heap-sort, the complexity becomes O(k).