Day 2 of DSA: Diving into Arrays

Welcome to my second day of learning Data Structures and Algorithms (DSA)! Today, I delved into arrays, a fundamental data structure that serves as a building block for many other structures and algorithms. Here’s a detailed summary of what I covered, complete with examples, explanations, and solutions to the exercises.

## Creating an Array

An array is a collection of elements, all of the same type, stored in contiguous memory locations. This allows for efficient access to elements using an index. Here’s a simple example in Python:

```python

# Creating an array

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

# Accessing elements

print(arr[0]) # Output: 1

print(arr[4]) # Output: 5

```

### Exercise 1

Create an array of your favorite fruits and access the first and last elements.

**Solution:**

```python

# Creating an array of fruits

fruits = ["Apple", "Banana", "Cherry", "Date", "Elderberry"]

# Accessing the first and last elements

print(fruits[0]) # Output: Apple

print(fruits[-1]) # Output: Elderberry

```

## Input and Output of an Array

Taking input for an array and printing its elements are basic operations you'll often perform. Here’s a quick demonstration:

```python

# Taking input for an array

arr = list(map(int, input("Enter numbers separated by space: ").split()))

# Printing the array

print("Array elements are:", arr)

```

### Exercise 2

Write a program to take an array of integers as input and print its elements.

**Solution:**

```python

# Taking input from user

arr = list(map(int, input("Enter integers separated by space: ").split()))

# Printing the array elements

print("Array elements are:", arr)

```

## Finding the Largest Element in an Array

To find the largest element in an array, you can iterate through the array and keep track of the maximum value found so far.

```python

def find_largest(arr):

max_element = arr[0]

for num in arr:

if num > max_element:

max_element = num

return max_element

arr = [10, 20, 4, 45, 99]

print("Largest element is:", find_largest(arr)) # Output: 99

```

### Exercise 3

Modify the program to find the smallest element in an array.

**Solution:**

```python

def find_smallest(arr):

min_element = arr[0]

for num in arr:

if num < min_element:

min_element = num

return min_element

arr = [10, 20, 4, 45, 99]

print("Smallest element is:", find_smallest(arr)) # Output: 4

```

## Arrays Are Passed by Reference

In Python, when you pass an array to a function, you're actually passing a reference to the original array, not a copy. This means changes made to the array within the function will affect the original array.

```python

def modify_array(arr):

arr[0] = 100

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

modify_array(arr)

print(arr) # Output: [100, 2, 3, 4, 5]

```

## Space and Time Complexity

Understanding the space and time complexity of array operations is crucial for writing efficient code. Here are some basic complexities:

- Accessing an element: O(1)

- Inserting or deleting an element at the end: O(1)

- Inserting or deleting an element at the beginning or middle: O(n)

- Finding an element: O(n)

## Linear Search

Linear search is the simplest search algorithm. It checks each element of the array until the target element is found or the array ends.

```python

def linear_search(arr, target):

for i in range(len(arr)):

if arr[i] == target:

return i

return -1

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

target = 3

print("Element found at index:", linear_search(arr, target)) # Output: 2

```

### Exercise 4

Write a program to implement linear search for a string array.

**Solution:**

```python

def linear_search_string(arr, target):

for i in range(len(arr)):

if arr[i] == target:

return i

return -1

arr = ["apple", "banana", "cherry", "date", "elderberry"]

target = "cherry"

print("Element found at index:", linear_search_string(arr, target)) # Output: 2

```

## Reversing an Array with Extra Space

You can reverse an array by creating a new array and filling it with elements from the original array in reverse order.

```python

def reverse_array(arr):

reversed_arr = [0] * len(arr)

for i in range(len(arr)):

reversed_arr[i] = arr[len(arr) - 1 - i]

return reversed_arr

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

print("Reversed array:", reverse_array(arr)) # Output: [5, 4, 3, 2, 1]

```

### Exercise 5

Reverse an array of strings using extra space.

**Solution:**

```python

def reverse_array_strings(arr):

reversed_arr = [0] * len(arr)

for i in range(len(arr)):

reversed_arr[i] = arr[len(arr) - 1 - i]

return reversed_arr

arr = ["apple", "banana", "cherry", "date", "elderberry"]

print("Reversed array:", reverse_array_strings(arr)) # Output: ["elderberry", "date", "cherry", "banana", "apple"]

```

## Reversing an Array Without Extra Space (Two-Pointer Approach)

You can reverse an array in place using the two-pointer approach, which swaps elements from the beginning and end moving towards the center.

```python

def reverse_in_place(arr):

left, right = 0, len(arr) - 1

while left < right:

arr[left], arr[right] = arr[right], arr[left]

left += 1

right -= 1

return arr

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

print("Reversed array:", reverse_in_place(arr)) # Output: [5, 4, 3, 2, 1]

```

### Exercise 6

Implement the two-pointer approach to reverse an array of characters.

**Solution:**

```python

def reverse_in_place_strings(arr):

left, right = 0, len(arr) - 1

while left < right:

arr[left], arr[right] = arr[right], arr[left]

left += 1

right -= 1

return arr

arr = ["a", "b", "c", "d", "e"]

print("Reversed array:", reverse_in_place_strings(arr)) # Output: ["e", "d", "c", "b", "a"]

```

## Binary Search

Binary search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half.

```python

def binary_search(arr, target):

left, right = 0, len(arr) - 1

while left <= right:

mid = (left + right) // 2

if arr[mid] == target:

return mid

elif arr[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1

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

target = 4

print("Element found at index:", binary_search(arr, target)) # Output: 3

```

### Exercise 7

Modify the binary search program to work with an array of strings.

**Solution:**

```python

def binary_search_strings(arr, target):

left, right = 0, len(arr) - 1

while left <= right:

mid = (left + right) // 2

if arr[mid] == target:

return mid

elif arr[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1

arr = ["apple", "banana", "cherry", "date", "elderberry"]

target = "date"

print("Element found at index:", binary_search_strings(arr, target)) # Output: 3

```

## Conclusion

Arrays are a versatile and essential data structure in programming. Today, I learned about creating arrays, finding the largest element, passing arrays by reference, and understanding basic space and time complexities. I also explored linear and binary search algorithms and different methods to reverse arrays. I look forward to diving deeper into more complex data structures and algorithms in the coming days!

Stay tuned for more updates on my DSA journey. Happy coding!