First and Last Occurrence of Element in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the first occurrence index of a target element in an array.

DSA Typescript

function firstOccurrence(arr: number[], target: number): number {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === [1]) {
      return i;
    }
  }
  return -1;
}

Drag options to blanks, or click blank then click option'

Aarr

Bi

Ctarget

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'i' instead of 'target' in the comparison.

Comparing arr[i] with arr instead of target.

We compare each element arr[i] with the target to find the first occurrence index.

2fill in blank

medium

Complete the code to find the last occurrence index of a target element in an array.

DSA Typescript

function lastOccurrence(arr: number[], target: number): number {
  for (let i = arr.length - 1; i >= 0; i--) {
    if (arr[i] === [1]) {
      return i;
    }
  }
  return -1;
}

Drag options to blanks, or click blank then click option'

Atarget

Barr

Ci

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'arr' instead of 'target' in the comparison.

Looping forward instead of backward.

We compare each element arr[i] with the target starting from the end to find the last occurrence index.

3fill in blank

hard

Fix the error in the binary search code to find the first occurrence of target in a sorted array.

DSA Typescript

function firstOccurrenceBinarySearch(arr: number[], target: number): number {
  let low = 0;
  let high = arr.length - 1;
  let result = -1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
      result = mid;
      high = [1];
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return result;
}

Drag options to blanks, or click blank then click option'

Amid + 1

Blow + 1

Chigh - 1

Dmid - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting high = mid + 1 which moves right instead of left.

Setting low incorrectly after finding target.

To find the first occurrence, after finding target at mid, we move high to mid - 1 to search left side.

4fill in blank

hard

Fill both blanks to complete the binary search code to find the last occurrence of target in a sorted array.

DSA Typescript

function lastOccurrenceBinarySearch(arr: number[], target: number): number {
  let low = 0;
  let high = arr.length - 1;
  let result = -1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
      result = mid;
      low = [1];
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = [2];
    }
  }
  return result;
}

Drag options to blanks, or click blank then click option'

Amid + 1

Bmid - 1

Chigh - 1

Dlow + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping low and high updates.

Not updating low or high correctly after finding target.

To find last occurrence, after finding target at mid, move low to mid + 1 to search right side; else adjust high to mid - 1.

5fill in blank

hard

Fill all three blanks to create a function that returns both first and last occurrence indices of target in a sorted array using binary search.

DSA Typescript

function firstAndLastOccurrence(arr: number[], target: number): {first: number, last: number} {
  let low = 0, high = arr.length - 1;
  let first = -1, last = -1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
      first = mid;
      high = [1];
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  low = 0;
  high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
      last = mid;
      low = [2];
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = [3];
    }
  }
  return {first, last};
}

Drag options to blanks, or click blank then click option'

Amid - 1

Bmid + 1

Chigh - 1

Dlow + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up low and high updates in the two searches.

Not resetting low and high before second search.

For first occurrence, move high to mid - 1; for last occurrence, move low to mid + 1; else adjust high to mid - 1.

Practice

1. What does the "First and Last Occurrence of Element" problem ask you to find in an array?

easy

A. The maximum element in the array

B. The sum of all elements in the array

C. The first and last positions where a given element appears

D. The number of unique elements in the array

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the first and last index positions of a specific element in an array.

2. Step 2: Identify what is required

   We need to locate where the element appears first and last, not sums or counts.

3. Final Answer:

   The first and last positions where a given element appears -> Option C

4. Quick Check:

   First and last occurrence = positions of element [OK]

Hint: Look for positions of element, not sums or counts [OK]

Common Mistakes:

• Confusing occurrence with sum or max
• Thinking about unique elements instead
• Ignoring the order of elements

2. Which of the following TypeScript function signatures correctly represents a function to find first and last occurrence of a number in an array?

easy

A. function findOccurrences(arr: number[], target: number): number

B. function findOccurrences(arr: string[], target: string): number

C. function findOccurrences(arr: number, target: number): number[]

D. function findOccurrences(arr: number[], target: number): [number, number]

Solution

1. Step 1: Analyze the function parameters

   The function should take an array of numbers and a target number to find.

2. Step 2: Analyze the return type

   We want to return two numbers (first and last index), so a tuple [number, number] is appropriate.

3. Final Answer:

   function findOccurrences(arr: number[], target: number): [number, number] -> Option D

4. Quick Check:

   Input array and target, output tuple of two indexes [OK]

Hint: Return a tuple of two numbers for first and last indexes [OK]

Common Mistakes:

• Using wrong input types like single number instead of array
• Returning only one number instead of two
• Returning array of wrong type

3. What will be the output of the following TypeScript code?

function findOccurrences(arr: number[], target: number): [number, number] {
  let first = -1;
  let last = -1;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      if (first === -1) first = i;
      last = i;
    }
  }
  return [first, last];
}

console.log(findOccurrences([5, 3, 7, 3, 9], 3));

medium

A. [1, 3]

B. [3, 3]

C. [0, 4]

D. [-1, -1]

Solution

1. Step 1: Trace the loop to find first occurrence

   At index 1, element is 3 which matches target, so first = 1.

2. Step 2: Update last occurrence while looping

   At index 3, element is 3 again, so last = 3.

3. Final Answer:

   [1, 3] -> Option A

4. Quick Check:

   First = 1, Last = 3 [OK]

Hint: Track first when found, update last every time [OK]

Common Mistakes:

• Returning first occurrence twice
• Returning indexes of wrong elements
• Not updating last occurrence properly

4. Identify the bug in this TypeScript function to find first and last occurrence:

function findOccurrences(arr: number[], target: number): [number, number] {
  let first = 0;
  let last = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      if (first === 0) first = i;
      last = i;
    }
  }
  return [first, last];
}

medium

A. last should be initialized to -1 instead of 0

B. first initialized to 0 causes wrong first occurrence when target is at index 0

C. Loop should start from 1 instead of 0

D. Missing return type annotation

Solution

1. Step 1: Check initialization of first

   first is set to 0, so if target is at index 0, condition first === 0 is true initially, causing incorrect logic.

2. Step 2: Understand impact on first occurrence

   If target is at index 0, first will never update correctly because first === 0 is true initially, so first stays 0 even if target not found.

3. Final Answer:

   first initialized to 0 causes wrong first occurrence when target is at index 0 -> Option B

4. Quick Check:

   Initialize first to -1 to fix [OK]

Hint: Initialize first to -1 to detect if target found [OK]

Common Mistakes:

• Initializing first to 0 instead of -1
• Not handling target at index 0 correctly
• Assuming first occurrence is always > 0

5. Given a sorted array with possible duplicates, which approach is the most efficient to find the first and last occurrence of a target element?

hard

A. Use two binary searches: one for first occurrence, one for last occurrence

B. Traverse the array from start to end to find first and last occurrence

C. Sort the array again and then find the element

D. Use a hash map to store all occurrences and then find first and last

Solution

1. Step 1: Understand the array is sorted

   Since the array is sorted, binary search can be used to find elements efficiently.

2. Step 2: Use binary search twice

   One binary search finds the first occurrence, another finds the last occurrence, both in O(log n) time.

3. Step 3: Compare with other options

   Traversing is O(n), sorting again is unnecessary, hash map uses extra space and is less efficient.

4. Final Answer:

   Use two binary searches: one for first occurrence, one for last occurrence -> Option A

5. Quick Check:

   Binary search twice = efficient for sorted arrays [OK]

Hint: Use binary search twice for first and last positions [OK]

Common Mistakes:

• Using linear search on sorted array
• Sorting array again unnecessarily
• Using extra space with hash map