Take While and Drop While

Problem

Read numbers from the left while they are smaller than k. Print two lines: first the numbers that were read (the longest prefix of numbers smaller than k), then all the other numbers. Print the word empty for a line with no numbers.

Constraints

  • 1 <= n <= 10^5

Examples

Input

5
1 2 5 1 7
4

Output

1 2
5 1 7

Solutions

Best approachTime O(n)Space O(n)

Both parts depend on one thing: the first position that fails the test. We find it once (findFirst stops early) and cut the array there. Python has takewhile and dropwhile for exactly this.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Split a prefix.
 * Input   : n, the array, then k.
 * Output  : Two lines.
 * Approach: Stop at the first match.
 * Time    : O(n)
 * Space   : O(n)
 * 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: Find the first position that is NOT smaller than k. A stream stops at the first match (findFirst).
        int split = java.util.stream.IntStream.range(0, a.length).filter(i -> a[i] >= k).findFirst().orElse(a.length);
        // Step 2: Everything before the split is the "take while" part. Everything from the split is the "drop while" rest.
        String taken = java.util.Arrays.stream(a, 0, split).mapToObj(String::valueOf).collect(java.util.stream.Collectors.joining(" "));
        String rest = java.util.Arrays.stream(a, split, a.length).mapToObj(String::valueOf).collect(java.util.stream.Collectors.joining(" "));
        return new String[] {taken.isEmpty() ? "empty" : taken, rest.isEmpty() ? "empty" : rest};
    }

    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(String.join("\n", solve(a, k)));
    }
}
Hints (2)
  1. Does the search continue after the first failure?
  2. What if every number is smaller than k?