How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Two Sigma.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Two Sigma during technical interviews.

Implement merge sort and largest 1-rectangle

Quick Overview

This question evaluates proficiency in implementing and analyzing classic algorithms, specifically merge sort for array sorting and techniques for computing the largest all-ones rectangular submatrix in a binary matrix, testing algorithmic thinking, data structure manipulation, and time/space complexity reasoning.

Company: Two Sigma

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

The coding round included two algorithm questions: 1. Implement merge sort for an array of integers. Return the sorted array and explain its time and space complexity. 2. Given an `m x n` binary matrix containing only `0` and `1`, find the area of the largest rectangular submatrix consisting entirely of `1`s. Assume standard input sizes and focus on correctness and efficiency.

Quick Answer: This question evaluates proficiency in implementing and analyzing classic algorithms, specifically merge sort for array sorting and techniques for computing the largest all-ones rectangular submatrix in a binary matrix, testing algorithmic thinking, data structure manipulation, and time/space complexity reasoning.

Part 1: Implement Merge Sort for an Array of Integers

Given an array of integers, return a new array containing the same integers sorted in non-decreasing order. You should implement merge sort rather than using a built-in sorting function.

Constraints

0 <= len(nums) <= 100000
-10^9 <= nums[i] <= 10^9
Do not use built-in full-array sorting functions such as sorted(nums) or nums.sort().
The returned array must contain exactly the same elements as the input array.

Examples

Input: ([5, 2, 9, 1, 5, 6],)

Expected Output: [1, 2, 5, 5, 6, 9]

Explanation: The values are sorted in non-decreasing order, preserving duplicates.

Input: ([],)

Expected Output: []

Explanation: Edge case: an empty array is already sorted.

Input: ([42],)

Expected Output: [42]

Explanation: Edge case: a single-element array is already sorted.

Input: ([0, -3, 8, -1, -3],)

Expected Output: [-3, -3, -1, 0, 8]

Explanation: The algorithm must correctly handle negative numbers and duplicates.

Input: ([10, 9, 8, 7, 6],)

Expected Output: [6, 7, 8, 9, 10]

Explanation: A reverse-sorted array should be fully reordered.

Hints

Recursively split the array into two halves until each part has size 0 or 1.
The key step is merging two already-sorted halves in linear time.

Part 2: Find the Area of the Largest Rectangular Submatrix of 1s

Given an m x n binary matrix containing only 0s and 1s, find the area of the largest rectangular submatrix consisting entirely of 1s. The rectangle must be aligned with the rows and columns of the matrix.

Constraints

0 <= m <= 500
0 <= n <= 500
matrix is rectangular: every row has the same length
matrix[i][j] is either 0 or 1
An empty matrix or a matrix with zero columns has answer 0.

Examples

Input: ([[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]],)

Expected Output: 6

Explanation: The largest all-1 rectangle has area 6, covering 2 rows and 3 columns.

Input: ([],)

Expected Output: 0

Explanation: Edge case: an empty matrix contains no rectangle.

Input: ([[0, 0], [0, 0]],)

Expected Output: 0

Explanation: There are no 1s, so the maximum area is 0.

Input: ([[1, 1, 1], [1, 1, 1]],)

Expected Output: 6

Explanation: The entire 2 x 3 matrix is filled with 1s.

Input: ([[1, 0, 1, 1, 1]],)

Expected Output: 3

Explanation: In a single row, the largest all-1 rectangle is the longest consecutive run of 1s.

Hints

Treat each row as the base of a histogram where each column height counts consecutive 1s ending at that row.
For each histogram, use a monotonic increasing stack to find the largest rectangle in linear time.

Quick Overview