================================================================================
         DATA STRUCTURES AND ALGORITHMS (C)
         PRACTICAL LAB SESSION 1: Arrays & Algorithm Analysis
         State University of Zanzibar (SUZA)
================================================================================

OBJECTIVES:
- Understand array declaration, initialization, and traversal
- Perform insertion, deletion, and searching on arrays
- Work with 2D arrays (matrices)
- Analyze algorithm complexity (Big O)

================================================================================
PART A: ARRAY BASICS
================================================================================

1. Array Declaration & Traversal:
   Declare an array of 10 integers. Read values from user.
   Display all elements with their indices.
   void displayArray(int arr[], int n);

2. Array Insertion:
   Write a function to insert an element at a given position.
   void insertAt(int arr[], int *n, int pos, int value);
   Test: [10,20,30,40,50] insert 25 at position 2 -> [10,20,25,30,40,50]

3. Array Deletion:
   Write a function to delete an element at a given position.
   void deleteAt(int arr[], int *n, int pos);
   Test: [10,20,30,40,50] delete at position 1 -> [10,30,40,50]

4. Array Reversal:
   Reverse an array in-place using two pointers (indices).
   void reverseArray(int arr[], int n);
   Test: [1,2,3,4,5] -> [5,4,3,2,1]

5. Find Min and Max:
   Write a function that finds both minimum and maximum in a single pass.
   void findMinMax(int arr[], int n, int *min, int *max);
   Test: [3,7,1,9,4] -> min=1, max=9

================================================================================
PART B: ARRAY OPERATIONS
================================================================================

6. Linear Search:
   int linearSearch(int arr[], int n, int key);
   Return the index of key, or -1 if not found.
   Test: [5,3,8,1,9] key=8 -> 2

7. Frequency Count:
   Count the frequency of each element in the array.
   void frequencyCount(int arr[], int n);
   Test: [1,2,2,3,3,3,4] -> 1:1, 2:2, 3:3, 4:1

8. Merge Two Sorted Arrays:
   void mergeSorted(int a[], int m, int b[], int n, int result[]);
   Test: [1,3,5] + [2,4,6] -> [1,2,3,4,5,6]

9. Rotate Array:
   Rotate array left by k positions.
   void rotateLeft(int arr[], int n, int k);
   Test: [1,2,3,4,5] k=2 -> [3,4,5,1,2]

10. Remove Duplicates from Sorted Array:
    int removeDuplicates(int arr[], int n);
    Return new length. Modify array in-place.
    Test: [1,1,2,2,3,4,4] -> [1,2,3,4] return 4

11. Second Largest Element:
    int secondLargest(int arr[], int n);
    Test: [12,35,1,10,34,1] -> 34

================================================================================
PART C: 2D ARRAYS (MATRICES)
================================================================================

12. Matrix Input & Display:
    Read an MxN matrix and display it in tabular format.
    void displayMatrix(int mat[][10], int rows, int cols);

13. Matrix Addition:
    void addMatrices(int a[][10], int b[][10], int result[][10], int r, int c);
    Test: [[1,2],[3,4]] + [[5,6],[7,8]] = [[6,8],[10,12]]

14. Matrix Transpose:
    void transpose(int mat[][10], int result[][10], int r, int c);
    Test: [[1,2,3],[4,5,6]] -> [[1,4],[2,5],[3,6]]

15. Matrix Multiplication:
    void multiplyMatrices(int a[][10], int b[][10], int result[][10],
                          int r1, int c1, int r2, int c2);
    Test: [[1,2],[3,4]] * [[5,6],[7,8]] = [[19,22],[43,50]]

16. Sum of Diagonal Elements:
    int diagonalSum(int mat[][10], int n);
    Test: [[1,2,3],[4,5,6],[7,8,9]] -> primary=15, secondary=15

================================================================================
PART D: EXTRA PRACTICE (LeetCode / HackerRank Style)
================================================================================

17. [Easy] Two Sum (LeetCode 1)
    Given an array and target, find two indices whose values sum to target.
    void twoSum(int arr[], int n, int target, int *i, int *j);
    Test: [2,7,11,15] target=9 -> indices 0,1
    Hint: Use nested loops (brute force O(n^2)).

18. [Easy] Remove Duplicates from Sorted Array (LeetCode 26)
    Given sorted array, remove duplicates in-place.
    Return new length.
    Test: [0,0,1,1,1,2,2,3,3,4] -> [0,1,2,3,4] return 5

19. [Medium] Rotate Array (LeetCode 189)
    Rotate array to the right by k steps.
    void rotateRight(int arr[], int n, int k);
    Test: [1,2,3,4,5,6,7] k=3 -> [5,6,7,1,2,3,4]
    Hint: Use reversal algorithm.

20. [Medium] Maximum Subarray - Kadane's Algorithm (LeetCode 53)
    Find contiguous subarray with largest sum.
    int maxSubarraySum(int arr[], int n);
    Test: [-2,1,-3,4,-1,2,1,-5,4] -> 6 (subarray [4,-1,2,1])

21. [Medium] Move Zeroes (LeetCode 283)
    Move all zeroes to end, maintaining order of non-zero elements.
    void moveZeroes(int arr[], int n);
    Test: [0,1,0,3,12] -> [1,3,12,0,0]

22. [Hard] Median of Two Sorted Arrays (LeetCode 4)
    Find the median of two sorted arrays.
    float findMedian(int a[], int m, int b[], int n);
    Test: [1,3] + [2] -> 2.0

================================================================================