Frontend School

Validate Lens Order Sequence

DSA
easy

Validate Lens Order Sequence

Easy
Stack
Arrays

Overview

At Lenskart, efficient order fulfillment is crucial for customer satisfaction. Every lens added or removed from an order needs to follow a strict Last-In, First-Out (LIFO) protocol to maintain inventory accuracy and streamline packaging. This problem simulates a sequence of lens handling operations and requires you to validate if the sequence adheres to LIFO principles.

What you need to do / Task

You are given an array of integers, operations, representing a sequence of actions on a virtual stack of lenses. Your task is to implement a function that determines if this sequence of operations is valid according to LIFO rules.

Specifically:

  1. If operations[i] is a positive integer X (e.g., +5), it means lens X is added to the top of the stack.
  2. If operations[i] is a negative integer -X (e.g., -5), it means lens X is removed from the top of the stack. For this operation to be valid, the stack must not be empty, and the lens currently at the top of the stack must be X. If either condition is not met, the entire sequence is invalid.
  3. After processing all operations, if the stack is not empty, the sequence is still considered valid, as long as all individual pop operations were valid.

Return true if the entire sequence of operations is valid, and false otherwise.

Input & Output

  • Input:
    • operations: number[] - An array of integers representing the sequence of lens handling actions.
      • +X (positive integer) indicates adding lens X.
      • -X (negative integer) indicates removing lens X.
  • Output:
    • boolean - true if the sequence is valid according to the rules, false otherwise.

Clarifications

  • Empty operations array: If the input array operations is empty, the sequence is trivially valid.
  • Zero values: operations[i] will never be 0.
  • Duplicate additions: If lens X is added multiple times (e.g., [1, 1]), both additions are valid, and X simply occupies a new position on the stack.
  • Invalid removal: If a negative operation -X occurs when the stack is empty, or the top element is not X, the sequence is immediately invalid.

Examples

1

Example 1

Input:

operations = [1, 2, -2, -1]

Output:

true

Note:

Push 1, Push 2, Pop 2 (match), Pop 1 (match). All operations valid.

2

Example 2

Input:

operations = [1, 2, -1, -2]

Output:

false

Note:

Push 1, Push 2. Then try to Pop 1, but 2 is on top. Invalid operation.

3

Example 3

Input:

operations = [5, -5, 10]

Output:

true

Note:

Push 5, Pop 5 (match), Push 10. All operations valid.

4

Example 4

Input:

operations = [-3]

Output:

false

Note:

Attempt to pop -3 from an empty stack. Invalid operation.

Constraints

Constraints & Assumptions

  • 1 <= operations.length <= 10^4
  • -10^5 <= operations[i] <= 10^5
  • operations[i] != 0
  • Lens IDs are positive integers.
  • The stack can hold any number of lenses.

What interviewers evaluate

  • Correctness: Does the solution accurately implement LIFO logic for both adding and removing lenses?
  • Edge Cases: Is the solution robust to scenarios like an empty stack during a removal, or an empty input array?
  • Efficiency: Does the solution process the operations within acceptable time and space complexity limits?
  • Code Quality: Is the code clean, readable, well-structured, and easy to understand?

Loading editor...