3.47 Retrieve Elements K Times

3.47.1 Problem Metadata

  • Platform: Other
  • Difficulty: Easy
  • URL: N/A
  • Tags:
  • Techniques: Hash Table, Array

3.47.2 Description

Given an integer array (possibly with duplicates) and an integer k >= 1, return the elements whose k-th occurrence appears, preserving the original order of those k-th occurrences.

3.47.3 Examples

Input: nums = [1,2,3,4,2,1,1,3], k = 1
Output: [1,2,3,4]

Input: nums = [1,2,3,4,2,1,1,3], k = 2
Output: [2,1,3]

3.47.4 Constraints

  • 1 <= nums.length <= 10^5
  • k >= 1

3.47.5 Solution - Hash Map Counting

3.47.5.1 Walkthrough

Use a hash map to track how many times each value has appeared. When an element’s count becomes exactly k, append it to the result list to preserve insertion order.

3.47.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

3.47.5.3 Implementation Steps

  1. Initialize an empty HashMap<Integer, Integer> and an empty result list.
  2. For each element x in nums:
    1. Increment count[x].
    2. If count[x] == k, append x to result.
  3. Return result.

3.47.5.4 Code - Java

public List<Integer> kthOccurrences(int[] nums, int k) {
    List<Integer> result = new ArrayList<>();
    Map<Integer, Integer> counts = new HashMap<>();

    for (int num : nums) {
        int newCount = counts.getOrDefault(num, 0) + 1;
        counts.put(num, newCount);

        if (newCount == k) {
            result.add(num);
        }
    }

    return result;
}