[FEAT]: Contains Duplicate Implementation in Cairo

[coxmars]

Contains Duplicate Implementation in Cairo

📘 Description

Create an example that implements a solution to the "Contains Duplicate" problem in Cairo. This exercise involves checking if an array contains any duplicate values, which is a common operation in many algorithms and a frequent interview question.

✅ Acceptance Criteria

• Create an exercises/contains_duplicate folder inside scripts folder and there create a scarb project as the other scripts.
• Implement a function that takes an array of integers and returns:
  • true if any value appears at least twice in the array
  • false if every element is distinct
• Implement at least two different approaches:
  • A naive solution (e.g., using nested loops) for educational purposes
  • An optimized solution (e.g., using a set-like structure or sorting)
• Include comprehensive test cases covering all the examples and edge cases.
• Document the implementation with clear explanations of both approaches.
• Compare the time and space complexity of the different approaches.
• Discuss any Cairo-specific challenges or optimizations.

📚 Examples

Example 1:

Input: nums = [1,2,3,1]
Output: true
Explanation: The element 1 occurs at the indices 0 and 3.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: All elements are distinct.

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Explanation: The array contains multiple duplicate elements.

🌎 References

• https://book.cairo-lang.org/
• https://leetcode.com/problems/contains-duplicate/

📜 Additional Notes

• ⚠ Read our guidelines before applying.
• This is a beginner-friendly exercise that introduces set-like data structures or sorting algorithms in Cairo.
• Consider how to efficiently implement a set-like structure in Cairo for checking duplicates.

[petersdt]

I’m interested in this one. kindly assign me.

[GideonBature]

Is it okay if I take this?

I have experience writing Cairo, I really want to work on this, I have written some cairo script before and would love to take on this one. ETA: within 48 hrs.

Thank you!

[mariocodecr]

Hii! My name is Mario Araya, I’m a Software Developer with 2+ years of experience. I have worked with backend technologies such as Cairo, Java, and C#, as well as frontend development using React, NextJS, and JavaScript/TypeScript. I’ve made contributions to open-source projects, completed a Starknet Bootcamp, exercises on NodeGuardians, finished Starklings, and participated in multiple hackathons. I’m also a member of the Dojo Coding community here in Costa Rica.

I will start by creating a new Scarb project inside scripts/exercises/contains_duplicate. Implement two functions: one naive solution using nested loops to compare each element with every other (O(n²) time, O(1) space), and one optimized solution using a LegacyMap or similar set-like structure to track seen values while iterating through the array (O(n) time, O(n) space). Write unit tests for each function covering empty arrays, single-element arrays, arrays with all distinct values, and arrays with one or more duplicates. In the module documentation, explain both approaches, their trade-offs in time and space complexity, and any Cairo-specific challenges such as limitations with dynamic data structures or memory management.

[coxmars]

hi @mariocodecr any updates?