Number of Equal Numbers Blocks - Practice Coding Problems

Number of Equal Numbers Blocks - Problem

You are given a 0-indexed array of integers, nums. The following property holds for nums: All occurrences of a value are adjacent. In other words, if there are two indices i < j such that nums[i] == nums[j], then for every index k that i < k < j, nums[k] == nums[i].

Since nums is a very large array, you are given an instance of the class BigArray which has the following functions:

int at(long long index): Returns the value of nums[index]
void size(): Returns nums.length

Let's partition the array into maximal blocks such that each block contains equal values. Return the number of these blocks.

Note: If you want to test your solution using a custom test, behavior for tests with nums.length > 10 is undefined.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,1,3,3,2,2]

› Output: 3

💡 Note: Three blocks: [1,1], [3,3], [2,2]. Each block contains equal adjacent values.

Example 2 — Single Elements

$ Input: nums = [1,2,3,4]

› Output: 4

💡 Note: Four blocks: [1], [2], [3], [4]. Each element forms its own block.

Example 3 — All Same

$ Input: nums = [5,5,5,5,5]

› Output: 1

💡 Note: One block: [5,5,5,5,5]. All elements are the same.

Constraints

1 ≤ nums.length ≤ 10¹⁵
1 ≤ nums[i] ≤ 100
All occurrences of each value are adjacent

Visualization

Tap to expand

Understanding the Visualization

Input

Array with grouped equal values: [1,1,3,3,2,2]

Process

Find boundaries where values change

Output

Count of blocks: 3

Key Takeaway

🎯 Key Insight: Since equal values are adjacent, we only need to count where values change to find block boundaries

Asked in

G Google 15 f Facebook 8 M Microsoft 6

The key insight is that since equal values are grouped together, we only need to find where each group ends. The linear scan approach compares adjacent elements to count transitions. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Optimization	O(n log n)	O(1)	Use binary search to find the end of each block efficiently
Linear Scan	O(n)	O(1)	Check each position to find where value blocks end

Binary Search Optimization — Algorithm Steps

Start at index 0
Use binary search to find end of current block
Jump to start of next block
Repeat until end of array

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Block

Current value = nums[i]

Binary Search

Find rightmost position with same value

Jump

Move to start of next block

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* arr;
    int length;
} BigArray;

int at(BigArray* ba, long long index) {
    return ba->arr[index];
}

int size(BigArray* ba) {
    return ba->length;
}

int solution(BigArray* bigArray) {
    int n = size(bigArray);
    if (n == 0) return 0;
    
    int blocks = 0;
    int i = 0;
    
    while (i < n) {
        int currentVal = at(bigArray, i);
        
        // Binary search for rightmost occurrence
        int left = i, right = n - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (at(bigArray, mid) == currentVal) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        blocks++;
        i = left + 1;
    }
    
    return blocks;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    BigArray ba;
    ba.arr = malloc(100 * sizeof(int));
    ba.length = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token != NULL) {
            ba.arr[ba.length++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int result = solution(&ba);
    printf("%d\n", result);
    
    free(ba.arr);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

For each of n positions, binary search takes O(log n) time

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.4K Views

Medium Frequency

~15 min Avg. Time

187 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler