CodingGyan

Remove All Copies of a Value

easy Arrays

Problem

Remove every number equal to k from the array and print the remaining numbers in their original order, separated by spaces. If nothing is left, print empty. Try to do it in one pass.

Constraints

  • 1 <= n <= 10^5
  • |a[i]|, |k| <= 10^9

Examples

Input

4
3 2 2 3
3

Output

2 2

Solutions

Best approachTime O(n)Space O(1)

Two indexes walk through the array. The read index looks at every number, the write index marks where the next kept number goes. No second array is needed in the original, so extra memory is O(1).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Remove a value.
 * Input   : n, the array, then k.
 * Output  : The remaining numbers.
 * Approach: Read and write pointers.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String solve(int[] a, int k) {
        // Step 1: "write" is the place for the next number we keep. Everything before it is already final.
        int write = 0;
        int[] data = a.clone();
        for (int read = 0; read < data.length; read++) {
            // Step 2: Copy only numbers that are not k.
            if (data[read] != k) {
                data[write++] = data[read];
            }
        }
        // Step 3: The first "write" places hold the answer.
        if (write == 0) {
            return "empty";
        }
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < write; i++) {
            if (i > 0) {
                result.append(' ');
            }
            result.append(data[i]);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        System.out.println(solve(a, k));
    }
}
Hints (2)
  1. Which index moves on every step?
  2. When does the write index move?

Try these next