Frontend School

Consolidate Feed Events

DSA
easy

Consolidate Feed Events

Easy
Arrays
Two Pointers
In-place

Overview

Imagine you're building a feature for a social media feed. To ensure a clean and engaging user experience, we want to prevent the feed from becoming noisy due to rapid-fire, identical actions. For example, if a user repeatedly likes and unlikes a post, we might only want to show a single 'liked' event if they end up liking it.

This problem focuses on a simpler version: consolidating consecutive identical events in a user's chronological feed history. The goal is to reduce visual clutter by ensuring that any sequence of identical events is represented by just one entry.

What you need to do / Task

Given a sorted array of event IDs, eventIds, representing a user's chronological feed history, modify the array in-place such that all consecutive duplicate event IDs are removed, leaving only one instance of each. The relative order of the unique event IDs should be preserved. Your function should return the new length of the modified array.

Input & output

  • eventIds: An array of integers, sorted in non-decreasing order, where each integer represents a unique event ID.
  • Return: An integer representing the new length of the array after consolidation. The modified eventIds array should contain the consolidated events in its first new_length positions. The elements beyond the new length do not matter.

Clarifications

  • Empty input: If eventIds is empty, the function should return 0.
  • No duplicates: If there are no consecutive duplicates in the array (e.g., [1, 2, 3]), the array should remain unchanged, and its original length should be returned.
  • Non-consecutive duplicates: Only consecutive duplicates should be consolidated. For example, [1, 2, 1] should remain [1, 2, 1] as the 1s are not consecutive.
  • Data type: Event IDs are integers, which can be positive, negative, or zero.

Examples

1

Example 1

Input:

eventIds = [1, 1, 2, 3, 3, 3, 4, 4]

Output:

5

Note:

The array eventIds is modified in-place. The first 5 elements become [1, 2, 3, 4, 4]. The new length is 5.

2

Example 2

Input:

eventIds = [5, 5, 5, 5]

Output:

1

Note:

The array eventIds is modified in-place. The first element becomes [5]. The new length is 1.

3

Example 3

Input:

eventIds = [1, 2, 3]

Output:

3

Note:

No consecutive duplicates found. The array remains [1, 2, 3]. The new length is 3.

Constraints

Constraints & assumptions

  • 0 <= eventIds.length <= 10^5
  • -10^9 <= eventIds[i] <= 10^9
  • eventIds is sorted in non-decreasing order.
  • The solution must modify the input array eventIds in-place.
  • The solution should use O(1) extra space.

Out of scope

  • Handling unsorted eventIds arrays.
  • Consolidating non-consecutive duplicate events (e.g., [1,2,1] should remain [1,2,1]).
  • Optimizing for non-integer event IDs or very large ID ranges that exceed standard integer types.

What interviewers evaluate

  • Correctness: The solution accurately consolidates consecutive duplicates and returns the correct new length.
  • Efficiency: The solution uses optimal time complexity (O(N)) and space complexity (O(1)).
  • In-place modification: The array is modified correctly without using additional data structures beyond a few pointers.
  • Edge cases: Handles empty arrays, arrays with no duplicates, and arrays with all duplicates correctly.

Loading editor...