First and Last Occurrence of Element in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find first and last occurrence of 3 in a sorted array

What is the output of the following TypeScript code that finds the first and last occurrence of the number 3 in the array?

DSA Typescript

function firstAndLastOccurrence(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];
}

const arr = [1, 2, 3, 3, 3, 4, 5];
console.log(firstAndLastOccurrence(arr, 3));

A [2, 4]

B [1, 3]

C [3, 5]

D [-1, -1]

💡 Hint

Look for the first and last index where the target appears in the array.

The function scans the array once. It sets 'first' when it finds the target the first time and updates 'last' every time it finds the target. For target 3, first occurrence is at index 2 and last at index 4.

❓ Predict Output

intermediate

Output when target is not in the array

What will the output be when searching for 6 in the array using the same function?

DSA Typescript

function firstAndLastOccurrence(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];
}

const arr = [1, 2, 3, 3, 3, 4, 5];
console.log(firstAndLastOccurrence(arr, 6));

A [0, 0]

B [-1, -1]

C [6, 6]

D [null, null]

💡 Hint

If the target is not found, the function returns [-1, -1].

Since 6 is not in the array, 'first' and 'last' remain -1, so the function returns [-1, -1].

🔧 Debug

advanced

Identify the error in binary search for first occurrence

What error does the following TypeScript code produce when trying to find the first occurrence of a target using binary search?

DSA Typescript

function firstOccurrence(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 = mid - 1; // Move left to find first occurrence
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return result;
}

console.log(firstOccurrence([1,2,3,3,3,4,5], 3));

A Infinite loop

B Returns -1 always

C SyntaxError due to missing semicolon

D Returns 4 (last occurrence) instead of first

💡 Hint

Check how 'high' is updated when target is found.

The original code incorrectly moves 'high' to mid + 1, which searches right side, so it finds last occurrence instead of first.

❓ Predict Output

advanced

Output of last occurrence binary search

What is the output of this code that finds the last occurrence of 3 in the array using binary search?

DSA Typescript

function lastOccurrence(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 = mid + 1; // Move right to find last occurrence
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return result;
}

console.log(lastOccurrence([1,2,3,3,3,4,5], 3));

A 4

B 2

C -1

D 3

💡 Hint

The function moves 'low' to mid + 1 when target is found to find last occurrence.

The last occurrence of 3 is at index 4, so the function returns 4.

🧠 Conceptual

expert

Time complexity of finding first and last occurrence using binary search

What is the time complexity of finding both the first and last occurrence of an element in a sorted array using binary search?

A O(n log n)

B O(n)

C O(log n)

D O(1)

💡 Hint

Each binary search takes logarithmic time, and you do two searches.

Finding first and last occurrence requires two binary searches, each O(log n), so total is O(log n).