CodingGyan

First Value Greater Than k (Optional)

easy Generics, Lambdas and Streams

Problem

Print the first value in the array (from left to right) that is greater than k. If there is none, print not found. Show the possibly missing result with Optional (Java), undefined (JavaScript) or None (Python) instead of a magic number like -1.

Constraints

  • 1 <= n <= 10^5

Examples

Input

4
1 5 3 9
4

Output

5

Solutions

Best approachTime O(n)Space O(1)

A result like -1 can be a real value in the data. Optional / undefined / None says clearly that nothing was found. Never test the found value with if (found), because 0 is false.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Find the first greater value.
 * Input   : n, n integers, then k.
 * Output  : The value or not found.
 * Approach: Optional style.
 * 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: Optional is a box that has a value or is empty. It forces the caller to think about "no result".
        java.util.Optional<Integer> found = java.util.Arrays.stream(a).filter(value -> value > k).boxed().findFirst();

        // Step 2: orElse gives a default text when the box is empty. map changes the value inside the box.
        return found.map(String::valueOf).orElse("not found");
    }

    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 (1)
  1. Why is -1 a bad marker here?

Try these next