# Arrays and Tuple in Python

An **array** is a continuous block of memory used to store similar or structured data.

Arrays allow **easy and fast access** to elements using an index, which makes them one of the most important data structures in DSA.

In Python, we don’t have traditional arrays like in C++ or Java.  
Instead, we use something called a **<mark>List</mark>**.

## Python Lists (Dynamic Arrays)

In Python, a list is a **dynamic array**.

### Example:

```python
arr = [1, 2, 3, 4, 5]
```

### **Key Characteristics:**

* Lists are **mutable** → They can be changed after declaration.
    
* They are **dynamic** → Their size can grow or shrink.
    
* They allow **index-based access** → `arr[0]`, `arr[1]`, etc.
    

---

## Static vs Dynamic Arrays

### 🔹 Static Array

* Size is fixed.
    
* Cannot grow after creation.
    
* Example: Arrays in C++
    

### 🔹 Dynamic Array (Python List)

* Size can increase or decrease.
    
* Memory is managed automatically.
    
* Used in almost all DSA problems in Python.
    

---

## Important List Operations

### 1️⃣ Access by Index → **O(1)**

```python
arr[2]
```

Accessing an element using an index is constant time.

---

### 2️⃣ Searching for an Element → **O(N)**

```python
if 5 in arr:
    print(True)
```

This takes **O(N)** time because Python needs to traverse the list element by element.

---

### 3️⃣ Important Dynamic Array Methods

#### ✅ `append()` → O(1) (Amortized)

```python
arr.append(6)
```

* Adds an element to the end.
    
* Amortized O(1) means most of the time it is constant time.
    
* Occasionally, resizing happens internally, which takes O(N), but overall average remains O(1).
    

---

#### ✅ `pop()` → O(1)

```python
arr.pop()
```

* Removes the last element.
    
* Constant time operation.
    

⚠️ `pop(index)` is O(N) because shifting is required.

---

#### ✅ `insert(index, value)` → O(N)

```python
arr.insert(2, 10)
```

* Inserts element at a specific position.
    
* All elements after that index need to shift.
    
* Therefore, time complexity is O(N).
    

---

#### ✅ `len()` → O(1)

```python
len(arr)
```

* Returns the number of elements in the list.
    
* Constant time operation.
    

---

## Why Arrays (Lists) Are Extremely Important in DSA

Most beginner DSA problems are based on arrays:

* Two Sum
    
* Sliding Window
    
* Prefix Sum
    
* [Kadane’s Algorithm](https://neetcode.io/courses/advanced-algorithms/0)
    
* Sorting
    
* Binary Search
    

---

# Tuples

A **tuple** in Python is an ordered collection of elements, just like a list.

However, the key difference is:

👉 **<mark>Tuples are immutable.</mark>**

Once a tuple is created, its values cannot be changed.

## How to Create a Tuple

```python
t = (1, 2, 3, 4)
```

You can also create a tuple without parentheses:

```python
t = 1, 2, 3
```

---

## Tuple vs List (Important Difference)

| Feature | List | Tuple |
| --- | --- | --- |
| Mutable | ✅ Yes | ❌ No |
| Syntax | `[ ]` | `( )` |
| Performance | Slightly slower | Slightly faster |
| Use Case | When data may change | When data should not change |

---

## Why Tuples Matter in DSA

Although tuples are not used as frequently as lists in basic DSA problems, they are very useful in certain scenarios:

### 1️⃣ Returning Multiple Values from a Function

```python
def min_max(arr):
    return (min(arr), max(arr))
```

### 2️⃣ Storing Fixed Data

For example:

* Coordinates → `(x, y)`
    
* Graph edges → `(node1, node2)`
    
* Key-value pairs
    

---

## Important Interview Insight ⚡

### 🔹 Tuples are Hashable (if elements are immutable)

This means they can be used as keys in dictionaries or stored inside sets.

Example:

```python
visited = set()
visited.add((1, 2))
```

This is very common in:

* Graph problems
    
* Grid-based problems
    
* Backtracking problems
    

Lists cannot be used as dictionary keys because they are mutable.

---

## Time Complexity

* Index access → **O(1)**
    
* Searching → **O(N)**
    
* No append, insert, or remove (because immutable)
    

---

## When Should You Use a Tuple?

Use a tuple when:

* Data should not change
    
* You want slightly better performance
    
* You need to use the value as a dictionary key
    
* You are returning multiple values from a function
    

---

## Key Takeaway

Tuples are like "fixed lists."  
They protect your data from accidental modification and are especially useful in hashing-related problems in DSA.