First and Last Occurrence of Element in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does 'First Occurrence of Element' mean in an array?

It means the position (index) where the element appears for the very first time when reading the array from left to right.

beginner

What does 'Last Occurrence of Element' mean in an array?

It means the position (index) where the element appears for the very last time when reading the array from left to right.

intermediate

Why is it useful to find the first and last occurrence of an element?

Finding these helps us know the range where the element appears, which is useful for counting how many times it occurs or for searching efficiently.

intermediate

How can binary search help find the first and last occurrence of an element in a sorted array?

Binary search can be modified to continue searching even after finding the element, moving left to find the first occurrence or right to find the last occurrence, making it faster than checking every element.

intermediate

What is the time complexity of finding first and last occurrence using binary search?

The time complexity is O(log n) because binary search divides the search space in half each time.

What is the first occurrence of element 5 in the array [1, 3, 5, 5, 7]?

A 1

B 2

C 3

D 4

The element 5 first appears at index 2 (0-based indexing).

If an element does not exist in the array, what should the first and last occurrence functions return?

A -1

B 0

C Array length

D Null

Returning -1 indicates the element is not found in the array.

Which search method is faster for finding first and last occurrence in a sorted array?

A Linear Search

B Bubble Sort

C Binary Search

D Insertion Sort

Binary Search is faster (O(log n)) compared to Linear Search (O(n)) for sorted arrays.

What is the last occurrence of element 5 in the array [1, 3, 5, 5, 7]?

A 3

B 4

C 1

D 2

The element 5 last appears at index 3.

Which of these is NOT a valid approach to find first and last occurrence?

A Using two pointers

B Linear Scan

C Modified Binary Search

D Sorting the array again

Sorting again is unnecessary if the array is already sorted and does not help find occurrences.

Explain how to find the first occurrence of an element in a sorted array using binary search.

Think about narrowing down the search to the left side after finding the element.

Describe why finding both first and last occurrence is useful in counting element frequency.

Counting how many times an element appears is easier with these two positions.