Quick Overview

A coding question asking for the value that occupies more than half of the positions in an integer array, where such a value is guaranteed to exist. It tests array traversal, counting and reasoning about running time and extra space.

Find the Value That Fills More Than Half of an Integer Array

Company: ByteDance

Role: Site Reliability Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Given an integer array `nums`, return the value that occurs in more than half of its positions. Every input is guaranteed to contain such a value. ### Function Signature ```python def find_majority_value(nums: list[int]) -> int: ``` ### Rules - A value `v` qualifies when the number of indices `i` with `nums[i] == v` is strictly greater than `len(nums) / 2`, that is, when `2 * count > len(nums)`. - At most one value can occur in more than half of the positions, and the input guarantees that one does, so the answer is unique. - Return the value itself, not its index or its count. ### Constraints - `1 <= len(nums) <= 5 * 10^4` - `-10^9 <= nums[i] <= 10^9` - A qualifying value always exists. ### Examples **Example 1** ```text Input: nums = [4, 7, 4] Output: 4 ``` The value 4 occurs twice among three positions, and `2 * 2 = 4 > 3`. **Example 2** ```text Input: nums = [9, 9, 3, 9, 3, 3, 9] Output: 9 ``` The value 9 occurs four times among seven positions; 3 occurs only three times. **Example 3** ```text Input: nums = [-1] Output: -1 ``` A single element is always the answer.

Overview: A coding question asking for the value that occupies more than half of the positions in an integer array, where such a value is guaranteed to exist. It tests array traversal, counting and reasoning about running time and extra space.

Given an integer array `nums`, return the value that occurs in more than half of its positions. Every input is guaranteed to contain such a value. Implement `find_majority_value(nums)`, which receives the list of integers and returns that value as an integer. ### Rules - A value `v` qualifies when the number of indices `i` with `nums[i] == v` is strictly greater than `len(nums) / 2`, that is, when `2 * count > len(nums)`. - At most one value can occur in more than half of the positions, and the input guarantees that one does, so the answer is unique. - Return the value itself, not its index or its count. ### Constraints - `1 <= len(nums) <= 5 * 10^4` - `-10^9 <= nums[i] <= 10^9` - A qualifying value always exists. - Every element and the returned value fit in a signed 32-bit integer (no value can exceed 2^31 - 1), so Java and C++ use `int`. ### Examples **Example 1** ```text Input: nums = [4, 7, 4] Output: 4 ``` The value 4 occurs twice among three positions, and `2 * 2 = 4 > 3`. **Example 2** ```text Input: nums = [9, 9, 3, 9, 3, 3, 9] Output: 9 ``` The value 9 occurs four times among seven positions; 3 occurs only three times.

Constraints

  • 1 <= len(nums) <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
  • A qualifying value always exists: exactly one value v has 2 * count(v) > len(nums)
  • Every element and the answer fit in a signed 32-bit integer; no value can exceed 2^31 - 1

Examples

Input: ([4, 7, 4],)

Expected Output: 4

Explanation: Source example 1: 4 occurs twice among three positions and 2 * 2 = 4 > 3.

Input: ([9, 9, 3, 9, 3, 3, 9],)

Expected Output: 9

Explanation: Source example 2, narrowest odd margin: 9 occurs 4 of 7 times while 3 occurs 3 times.

Hints

  1. The qualifying test is 2 * count > len(nums); at most one value can pass it, and the input guarantees that one does.
  2. Think about what the guaranteed value implies for all the other values combined: together they fill fewer than half of the positions.
  3. Return the value itself, not its index or how many times it occurs.

Find the Value That Fills More Than Half of an Array

easyByteDanceSite Reliability Engineer

Given an integer array nums, return the value that occurs in more than half of its positions. Every input is guaranteed to contain such a value.

Implement find_majority_value(nums), which receives the list of integers and returns that value as an integer.

Rules

  • A value v qualifies when the number of indices i with nums[i] == v is strictly greater than len(nums) / 2, that is, when 2 * count > len(nums).
  • At most one value can occur in more than half of the positions, and the input guarantees that one does, so the answer is unique.
  • Return the value itself, not its index or its count.

Constraints

  • 1 <= len(nums) <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
  • A qualifying value always exists.
  • Every element and the returned value fit in a signed 32-bit integer (no value can exceed 2^31 - 1), so Java and C++ use int.

Examples

Example 1

Input:  nums = [4, 7, 4]
Output: 4

The value 4 occurs twice among three positions, and 2 * 2 = 4 > 3.

Example 2

Input:  nums = [9, 9, 3, 9, 3, 3, 9]
Output: 9

The value 9 occurs four times among seven positions; 3 occurs only three times.

Examples

Example 1
Input
([4, 7, 4],)
Output
4
Notes
Source example 1: 4 occurs twice among three positions and 2 * 2 = 4 > 3.
Example 2
Input
([9, 9, 3, 9, 3, 3, 9],)
Output
9
Notes
Source example 2, narrowest odd margin: 9 occurs 4 of 7 times while 3 occurs 3 times.

Constraints

  • •1 <= len(nums) <= 5 * 10^4
  • •-10^9 <= nums[i] <= 10^9
  • •A qualifying value always exists: exactly one value v has 2 * count(v) > len(nums)
  • •Every element and the answer fit in a signed 32-bit integer; no value can exceed 2^31 - 1

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def find_majority_value(nums: list[int]) -> int:
Sample call
find_majority_value([4, 7, 4])
Language
Case 1
Input
([4, 7, 4],)
Expected
4
Case 2
Input
([9, 9, 3, 9, 3, 3, 9],)
Expected
9

Browse More Questions

Show the approach

Approach

Algorithm (majority vote): scan the array once while keeping a candidate value and a counter. When the counter is 0, the current element becomes the new candidate with counter 1. Otherwise an element equal to the candidate increments the counter and a different element decrements it. After the scan, return the candidate.

Invariant: whenever the counter returns to 0, the elements processed since the previous reset can be split into pairs of two unequal values, so no single value fills more than half of that stretch. Within the current stretch, every element that differs from the candidate cancels one copy of the candidate, so the candidate is the only value that can fill more than half of the current stretch.

Correctness: let m be the value with 2 * count(m) > len(nums). Each completed stretch holds at most half copies of m, so after removing all completed stretches, m still fills more than half of the final stretch. In the final stretch only the candidate can do that, so the final candidate equals m. The input guarantees m exists, so no second verification pass is needed.

Edge cases: a single element is returned directly; an all-equal array keeps one candidate throughout; zero, negative values and the bounds -10^9 and 10^9 need no special handling because the algorithm only compares values for equality and never adds them, so nothing can overflow a 32-bit int.

Time complexity:
O(n)
Space complexity:
O(1)