AdventJS 2023: Day 1

Solution for Challenge #1 of AdventJS 2023

• Introduction
• Challenge Description
• Analysis
• Solution

Introduction

On December 1st, AdventJS started a series of challenges to practice and improve as a software developer. It consists of a new programming challenge being enabled every day, from December 1st until Christmas on the 25th. 🎄

Challenge Description

In the toy factory of the North Pole, each toy has a unique identification number.

However, due to an error in the toy machine, some numbers have been assigned to more than one toy.

Find the first identification number that has been repeated, where the second occurrence has the smallest index!

In other words, if there is more than one repeated number, you must return the number whose second occurrence appears first in the list. If there are no repeated numbers, return -1.

const giftIds = [2, 1, 3, 5, 3, 2]
const firstRepeatedId = findFirstRepeated(giftIds)
console.log(firstRepeatedId) // 3
// Even though 2 and 3 are repeated
// 3 appears second time first

const giftIds2 = [1, 2, 3, 4]
const firstRepeatedId2 = findFirstRepeated(giftIds2)
console.log(firstRepeatedId2) // -1
// It is -1 since no number is repeated

const giftIds3 = [5, 1, 5, 1]
const firstRepeatedId3 = findFirstRepeated(giftIds3)
console.log(firstRepeatedId3) // 5

Watch out! The elves say this is a Google technical test.

Analysis

The goal is to find the first repeated number where the second occurrence of that number has the lowest possible index in the list. If there are no repeated numbers, -1 will be returned.

Input

• A list of integer numbers (gifts), where each number represents a unique identifier of a toy.

Output

• The first identification number is repeated with the lowest index in its second appearance.

• -1 if there are no repeated numbers.

Conceptual Analysis

• The first repetition needs to be found, so it's not necessary to iterate more than once.

• We need an efficient way to keep track of the numbers already checked.

• We will stop execution when we find the first repeated number and return it.

Solution

By creating a Set, you can store the repeated values while traversing the array. Each stored element is evaluated, and upon finding a repetition, the answer is returned.

/**
 * Finds the first repeated gift in the given array.
 *
 * @param {number[]} gifts - The array of gifts to search for repeated items.
 * @returns {number} - The first repeated gift, or -1 if no repeated gift is found.
 */
function findFirstRepeated(gifts) {
  // Create a set to store unique gifts
  const set = new Set();

  // Iterate through the gifts array
  for (const gift of gifts) {
    // If the gift is already in the set, return it as the first repeated gift
    if (set.has(gift)) {
      return gift;
    }

    // Add the gift to the set
    set.add(gift);
  }

  // Return -1 if no repeated gift is found
  return -1;
}

Alternative Solutions

Here are some solutions provided by the community:

Solution by SantiMenendez19

function findFirstRepeated(gifts) {
  const repeated = gifts.filter((gift, i) => gifts.indexOf(gift) !== i)
  return repeated.length > 0 ? repeated[0] : -1
}

Solution by marta-vilaseca

function findFirstRepeated(gifts) {
  const unique = new Set();
  for (let i = 0; i < gifts.length; i++) {
    if (unique.has(gifts[i])) {
      return gifts[i];
    } else {
      unique.add(gifts[i]);
    }
  }
  return -1;
}

Do you have another alternative? Leave it in the comments!

Comments

[Obed Paz]

Good article, keep the hard work.

Here's mine:

function findFirstRepeated(gifts) {
  // Code here
  let checkedIds = [];
  let repeated = [];

  gifts.find(item => {
    if (checkedIds.includes(item)) {
      repeated.push(item);
      return item;
    }
    checkedIds.push(item);
  });

  return repeated.length > 0 ? repeated[0] : -1;
}