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 TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Find >n/3 elements in sorted array | TikTok Coding Question

Quick Overview

This TikTok software-engineer screen asks you to return every value occurring strictly more than n/3 times in a sorted array, in O(log n) time and O(1) space. The solution proves at most two such values can exist, samples the fixed positions n/3 and 2n/3, and confirms each candidate's count with lower_bound/upper_bound binary searches. It tests frequency reasoning on sorted data, combinatorial bounds, and rigorous complexity and edge-case analysis.

Find >n/3 elements in sorted array

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question Given a **sorted (non-decreasing)** integer array `A` of length `n`, return all distinct values that occur **strictly more than `n/3` times**. Design an algorithm that runs in **O(log n)** time and uses **O(1)** extra space. Answer the following: 1. Prove that there can be **at most two** such values. 2. Describe how to choose **candidate positions** and confirm each candidate's count using binary searches (e.g., `lower_bound` / `upper_bound`). 3. Provide a **correctness argument** and **time/space complexity** analysis. 4. Handle edge cases (e.g., `n < 3`, empty array, runs that straddle the boundary positions, all-equal arrays).

Quick Answer: This TikTok software-engineer screen asks you to return every value occurring strictly more than n/3 times in a sorted array, in O(log n) time and O(1) space. The solution proves at most two such values can exist, samples the fixed positions n/3 and 2n/3, and confirms each candidate's count with lower_bound/upper_bound binary searches. It tests frequency reasoning on sorted data, combinatorial bounds, and rigorous complexity and edge-case analysis.

Given a sorted (non-decreasing) integer array `A` of length `n`, return all distinct values that occur strictly more than `n/3` times. Return the qualifying values in the order they first appear in the array. Because the array is sorted, equal values form one contiguous block, and at most two distinct values can exceed the `n/3` threshold (three would sum to more than `n` elements). Aim for O(log n) time and O(1) extra space by sampling the two fixed positions `n/3` and `2*n/3`: any block longer than `n/3` must cover at least one of these positions. Confirm each candidate's count with binary search (`lower_bound` / `upper_bound`). Use the integer test `3 * count > n` to express "strictly more than n/3" without floating point, and deduplicate candidates so an all-equal array reports its value once. Examples: - A = [1, 2, 2, 2, 3] -> [2] (2 appears 3 times, 3 > 5/3) - A = [1, 1, 1, 2, 2, 2, 3] -> [1, 2] - A = [1, 2, 3, 4, 5, 6] -> [] - A = [5, 5, 5, 5, 5, 5] -> [5]

Constraints

0 <= n <= 10^6
A is sorted in non-decreasing order
-10^9 <= A[i] <= 10^9
At most two distinct values can satisfy the condition
Target O(log n) time and O(1) extra space (output excluded)

Examples

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

Expected Output: [2]

Explanation: n=5, threshold count>5/3. 2 appears 3 times (3>5/3), so [2].

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

Expected Output: [1, 2]

Explanation: n=7. 1 and 2 each appear 3 times (3>7/3); 3 appears once. Both qualify.

Input: ([1, 2, 3, 4, 5, 6],)

Expected Output: []

Explanation: n=6, every value appears once (1 is not > 2), so no qualifier.

Input: ([],)

Expected Output: []

Explanation: Empty array returns empty list.

Input: ([7],)

Expected Output: [7]

Explanation: n=1, single element has count 1 and 3*1>1, so it qualifies.

Input: ([5, 5, 5, 5, 5, 5],)

Expected Output: [5]

Explanation: All-equal: both sampled positions hold 5; dedup reports it once.

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

Expected Output: [-3]

Explanation: n=7. -3 appears 3 times (3*3=9>7); positions n/3=2 (-3) and 2n/3=4 (0). Only -3 qualifies.

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

Expected Output: []

Explanation: n=6, each value appears twice (2 is not > 2). No qualifier.

Input: ([2, 2],)

Expected Output: [2]

Explanation: n=2, 2 appears twice and 3*2=6>2, so it qualifies.

Hints

In a sorted array, all copies of a value are contiguous, so each value's count is upper_bound(v) - lower_bound(v).
If three distinct values each exceeded n/3, their disjoint counts would sum to more than n elements -- impossible. So at most two qualify.
Any contiguous block longer than n/3 cannot fit strictly between consecutive thirds, so it must cover A[n/3] or A[2n/3]. Only those two positions can host a qualifier.
Use the integer test 3 * count > n instead of count > n/3 to avoid floating point, and deduplicate the two sampled values for all-equal arrays.

Last updated: Jun 26, 2026

Loading coding console...

Quick Overview

Find >n/3 elements in sorted array

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Constraints

0 <= n <= 10^6
A is sorted in non-decreasing order
-10^9 <= A[i] <= 10^9
At most two distinct values can satisfy the condition
Target O(log n) time and O(1) extra space (output excluded)

Examples

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

Expected Output: [2]

Explanation: n=5, threshold count>5/3. 2 appears 3 times (3>5/3), so [2].

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

Expected Output: [1, 2]

Explanation: n=7. 1 and 2 each appear 3 times (3>7/3); 3 appears once. Both qualify.

Input: ([1, 2, 3, 4, 5, 6],)

Expected Output: []

Explanation: n=6, every value appears once (1 is not > 2), so no qualifier.

Input: ([],)

Expected Output: []

Explanation: Empty array returns empty list.

Input: ([7],)

Expected Output: [7]

Explanation: n=1, single element has count 1 and 3*1>1, so it qualifies.

Input: ([5, 5, 5, 5, 5, 5],)

Expected Output: [5]

Explanation: All-equal: both sampled positions hold 5; dedup reports it once.

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

Expected Output: [-3]

Explanation: n=7. -3 appears 3 times (3*3=9>7); positions n/3=2 (-3) and 2n/3=4 (0). Only -3 qualifies.

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

Expected Output: []

Explanation: n=6, each value appears twice (2 is not > 2). No qualifier.

Input: ([2, 2],)

Expected Output: [2]

Explanation: n=2, 2 appears twice and 3*2=6>2, so it qualifies.

Hints

In a sorted array, all copies of a value are contiguous, so each value's count is upper_bound(v) - lower_bound(v).
If three distinct values each exceeded n/3, their disjoint counts would sum to more than n elements -- impossible. So at most two qualify.
Any contiguous block longer than n/3 cannot fit strictly between consecutive thirds, so it must cover A[n/3] or A[2n/3]. Only those two positions can host a qualifier.
Use the integer test 3 * count > n instead of count > n/3 to avoid floating point, and deduplicate the two sampled values for all-equal arrays.

Last updated: Jun 26, 2026

Loading coding console...