# Lists, sets & time complexity

Code With Purpose · Hinglish · Free starter lesson

## Concept

List order preserve karti hai aur repeated values rakh sakti hai. Set unique, hashable values rakhta hai aur list jaisa ordering promise nahi karta. Sequence important ho toh list; uniqueness ya membership checks main kaam ho toh set consider karo.

Big-O input size n badhne par work ka growth batata hai, exact seconds nahi. Unsorted list search worst case mein O(n) hai. Typical hashing mein set membership average O(1) hota hai; worst case O(n) ho sakta hai. Set banane mein bhi time aur memory lagti hai.

Bahut membership checks hon toh ek baar set banana useful ho sakta hai. Har check par set dobara banana waste hai. Code duplicate values dhoondta hai aur har duplicate pehli baar encounter hone ka order preserve karta hai. Expected time O(n), extra storage O(n) hai.

## Example

```python
def find_duplicates(values):
    seen, reported = set(), set()
    duplicates = []
    for value in values:
        if value in seen and value not in reported:
            duplicates.append(value)
            reported.add(value)
        seen.add(value)
    return duplicates

print(find_duplicates([3, 1, 3, 2, 1, 3]))
```

## Expected output

```text
[3, 1]
```

## Exercise

Hashable values ke liye unique_in_order(values) likho. [4, 2, 4, 1, 2] check karo. list(set(values)) same order promise kyun nahi karta?

## Suggested solution

```
def unique_in_order(values):
    seen = set()
    result = []
    for value in values:
        if value not in seen:
            result.append(value)
            seen.add(value)
    return result

print(unique_in_order([4, 2, 4, 1, 2]))  # [4, 2, 1]
# Sets do not provide a sequence-order guarantee.
```

## Takeaway

Approaches compare karte waqt setup cost aur memory bhi count karo.

Reference: https://docs.python.org/3/tutorial/datastructures.html

https://codewithpurposeai.in/lesson-dsa-complexity.html?lang=hinglish