<h1
style="
display: flex;
align-items: center;
justify-content: center;"
>
DSaA Lab 1 - Arrays
</h1>

<h4 style="text-align: center;">
The Islamic University of Gaza<br>
Engineering Faculty<br>
Department of Computer Engineering
</h4>

<font color="#ec53c4">
Prepared by:
Eng. Ahmad Albarasy
</font>
<br>
<font color="#ec53c4">
Under the supervision of:
Prof. Ahmad Mahdi
</font>

---

In this lab, we are going to dive into arrays, one of the most basic yet fundamental data structures used in almost every peice of code we write. It serves as a ground base for implementing many more complex data structures that we will explore in later labs. But for now, lets get started!

## Definition & Usage

**An array** is a linear data structure that has **a fixed size** and stores elements of the same type (or memory size) in contiguous locations in memory. An array is stored such that the position (memory address) of each element can be computed from the base index using a simple mathematical formula.

<div style="
display:flex;
align-items: center;
justify-content: center;"
>


</div>

For instance, if we have an array that has a length of 5, and it stores elements of type `int`.

### Declaration and Initialization

To create an array in Java, we have to declare it first then we can initialize it with our size of choice:

int[] arr;
arr = new int[5];

We can both declare and initialize the array in one step:

int[] arr = new int[5];

Alternatively, we can directly specify the elements of the array, which also defines the size that is going to be used:

int[] arr = { 1, 2, 3, 4, 5 }; // arr.length = 5

### Accessing and Modifying Elements

To access the first element, we have to use index `0`, since Java is a zero-based indexing language (just like almost every other programming lanuage):

int firstInt = arr[0];

intuitively, to access the last element, we use the index `n-1`, where `n` is the length of the array:

int lastInt = arr[4];

**In Java**, if we attempt to access an index that are out of the array's boundaries, Java will throw an `ArrayIndexOutOfBoundsException` in runtime, resulting in crashing your program.

To modify an element, we can simply assign a value the index we are willing to modify:

arr[4] = 10; // our array becomes [1, 2, 3, 4, 10]

>[!Note] A side note
>The size of an integer varies depending on the programming language. Common integer sizes include 16-bit, 32-bit, and 64-bit. **In Java**, however, **the int type always occupies 4 bytes (32 bits)**, regardless of whether the system is 32-bit or 64-bit. This size is guaranteed across all Java Virtual Machine (JVM) implementations and platforms.

### Iterating through an array

Now, lets say that we want to iterate over the array and print its values. To do so, we use a simple for loop that starts from index `0`, and exits when the condition `index < length` is not met

public class Main {
  public static void main(String[]args){
    int[] arr = { 1, 2, 3, 4, 5 };
    for(int i = 0; i < arr.length; i++){
      System.out.println(arr[i]);
    }
  }
}

## Types of Arrays

**In terms of dimensions, arrays have 2 types:**

1. One Dimensional Array
A one dimensional array is, as the name implies, an array that has only one dimension to it, and it can be accessed using a single index. It is commonly used to store a collection of elements of the same type in an ordered sequence and perform operations on them.

short[] grades = { 60, 70, 80 };

2. Multi-Dimensional Array
A multi-dimensional array is an array that has more than one dimension. It can be thought of as an array of arrays, where each element of the main array is itself an array.

int[][] unityMatrix = {
  {1, 0, 0},
  {0, 1, 0},
  {0, 0, 1}
}

The most common type is the two-dimensional array, which can be visualized as a table or a grid with rows and columns. Multi-dimensional arrays are useful for representing matrices, game boards, or any data that naturally fits into a tabular structure.

## Real World Examples

Arrays are pretty much everywhere, you definitely have already used them in your previous programming course last year, but here are some real-world examples just for the sake of lab.

### Mapping indices to objects/values
It can be as simple as this, using an array to map an index to a specific value. For example, you can map the indices from `0` to `11` to the months of the year:

String[] months = {
  "Jan", "Feb", "Mar", "Apr", "May", "Jun",
  "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"
};

Another example would be mapping a vector of 3 elements representing an RGB color:

short[] color = {255, 0, 255} // magenta

### Matrix Multiplication
One of the practical uses of arrays, especially multi-dimensional ones, is to perform matrix multiplication. Take a look at this example, which multiplies a `2x3` matrix with a `3x2` one, resulting in a `2x2` resultant matrix:

public class MatrixMultiplication {
  public static void main(String[] args) {
    int[][] A = {
        { 1, 2, 3 },
        { 4, 5, 6 }
    };

    int[][] B = {
        { 7, 8 },
        { 9, 10 },
        { 11, 12 }
    };

    int[][] result = multiplyMatrices(A, B);

    System.out.println("Resultant Matrix:");
    printMatrix(result);
  }

  public static int[][] multiplyMatrices(int[][] A, int[][] B) {
    int rowsA = A.length;
    int colsA = A[0].length;
    int colsB = B[0].length;

    int[][] result = new int[rowsA][colsB];

    for (int i = 0; i < rowsA; i++) {
      for (int j = 0; j < colsB; j++) {
        for (int k = 0; k < colsA; k++) {
          result[i][j] += A[i][k] * B[k][j];
        }
      }
    }

    return result;
  }

  public static void printMatrix(int[][] matrix) {
    for (int[] row : matrix) {
      for (int value : row) {
        System.out.print(value + "\t");
      }
      System.out.println();
    }
  }
}

Matrix multiplication is used in a variety of applications, including image processing, graphics, video games, cheating in your linear algebra homework, physics simulations, computer vision, and machine learning algorithms such as neural networks

## Tasks

### Task 1 (4 points)

Write a program that reverses the order of numbers in an array in-place and prints out the result.

Use the following code to implement and submit your solution:

/* make sure to add this package identifier before you
 * submit your solution to GradeScope. Remove it while testing locally */
package com.gradescope.labOne;

public class TaskOne {
  public static void reverse(int[] arr){
    // implement your solution here
  }

}

You can use the following code to test your solution:

import java.util.Arrays;

public class TaskOneTests {
  public static void main(String[] args) {
    /* ---------- Test Case 1 ---------- */
    int[] arr1 = {1, 2, 3, 4, 5, 6};
    System.out.println("Original Array: " + Arrays.toString(arr1));
    TaskOne.reverse(arr1);
    System.out.println("Reversed Version: " + Arrays.toString(arr1));
    System.out.println("Expected: [6, 5, 4, 3, 2, 1]\n");

    /* ---------- Test Case 2 ---------- */
    int[] arr2 = {5, 4, 3, 2, 1};
    System.out.println("Original Array: " + Arrays.toString(arr2));
    TaskOne.reverse(arr2);
    System.out.println("Reversed Version: " + Arrays.toString(arr2));
    System.out.println("Expected: [1, 2, 3, 4, 5]\n");

    /* ---------- Test Case 3 ---------- */
    int[] arr3 = {42};
    System.out.println("Original Array: " + Arrays.toString(arr3));
    TaskOne.reverse(arr3);
    System.out.println("Reversed Version: " + Arrays.toString(arr3));
    System.out.println("Expected: [42]\n");

    /* ---------- Test Case 4 ---------- */
    int[] arr4 = {};
    System.out.println("Original Array: " + Arrays.toString(arr4));
    TaskOne.reverse(arr4);
    System.out.println("Reversed Version: " + Arrays.toString(arr4));
    System.out.println("Expected: []\n");

    /* ---------- Test Case 5 ---------- */
    int[] arr5 = {10, -5, 0, 8};
    System.out.println("Original Array: " + Arrays.toString(arr5));
    TaskOne.reverse(arr5);
    System.out.println("Reversed Version: " + Arrays.toString(arr5));
    System.out.println("Expected: [8, 0, -5, 10]\n");
  }
}

---

### Task 2 (3 points)

You are given an array of integers representing daily wind speeds in km/h.
A **calm period** is defined as a sequence of consecutive days where the wind speed never exceeds a certain threshold `T`

write a program that finds the longest calm period given an array representing the wind speeds over 15 days.

>[!Tip]
>Take a look at the sliding window approach, which is a common technique to solve some array-related problems. Give it a quick search :>

Use the following code to implement and submit your solution:

/* make sure to add this package identifier before you
 * submit your solution to GradeScope. Remove it while testing locally */
package com.gradescope.labOne;

public class TaskTwo {

    public static int longestCalmPeriod(int[] speeds, int T) {
        // implement your solution here
        return 0; // this is just a placeholder
    }
}

You can use the following code to test your solution:

public class TaskTwoTests {
  public static void main(String[] args) {
        /* ---------- Test Case 1 ---------- */
        int[] speeds1 = { 5, 8, 9, 3, 2, 1, 11, 4, 5, 13, 16, 14, 7, 2, 4 };
        int T1 = 8;
        int result1 = TaskTwo.longestCalmPeriod(speeds1, T1);
        System.out.println("Test Case 1:");
        System.out.println("Threshold: " + T1);
        System.out.println("Expected Output: 3");
        System.out.println("Your Output: " + result1);
        System.out.println();

        /* ---------- Test Case 2 ---------- */
        int[] speeds2 = { 10, 7, 6, 5, 12, 9, 3, 3, 4, 14, 4, 8, 8, 5, 7 };
        int T2 = 8;
        int result2 = TaskTwo.longestCalmPeriod(speeds2, T2);
        System.out.println("Test Case 2:");
        System.out.println("Threshold: " + T2);
        System.out.println("Expected Output: 5");
        System.out.println("Your Output: " + result2);
    }
}

---

### Task 3 (3 points)
Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to `target`.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

Question Link on [LeetCode](https://leetcode.com/problems/two-sum)

> **Example 1:**
Input: nums = `[2,7,11,15]`, target = `9`
Output: `[0,1]`
Explanation: Because `nums[0]` + `nums[1]` == `9`, we return `[0, 1]`.

> **Example 2:**
Input: nums = `[3,2,4]`, target = `6`
Output: `[1,2]`

> **Example 3:**
Input: nums = `[3,3]`, target = `6`
Output: `[0,1]`

Use the following code to implement and submit your solution:

/* make sure to add this package identifier before you
 * submit your solution to GradeScope. Remove it while testing locally */
package com.gradescope.labOne;

public class TaskThree {

  public static int[] twoSum(int[] nums, int target) {
    // implement your solution here
  }
}

Use the following code to test your solution. Alternatively, you can solve it on LeetCode to get used to it :)

import java.util.Arrays;

public class TaskThreeTests {
  public static void main(String[] args) {
    testSimpleCase();
    testPairAtEnds();
    testDuplicateValues();
    testNegativeNumbers();
  }

  public static void testSimpleCase() {
    int[] nums = {2, 7, 11, 15};
    int target = 9;
    int[] result = TaskThree.twoSum(nums, target);
    int[] expected = {0, 1};

    System.out.println("Test 1 - Simple Case");
    printResult(result, expected);
  }

  public static void testPairAtEnds() {
    int[] nums = {1, 2, 3, 4, 10};
    int target = 11;
    int[] result = TaskThree.twoSum(nums, target);
    int[] expected = {0, 4};

    System.out.println("Test 2 - Pair at Ends");
    printResult(result, expected);
  }

  public static void testDuplicateValues() {
    int[] nums = {3, 3, 4, 5};
    int target = 6;
    int[] result = TaskThree.twoSum(nums, target);
    int[] expected = {0, 1};

    System.out.println("Test 3 - Duplicate Values");
    printResult(result, expected);
  }

  public static void testNegativeNumbers() {
    int[] nums = {-1, 5, 1, 2};
    int target = 1;
    int[] result = TaskThree.twoSum(nums, target);
    int[] expected = {0, 3};

    System.out.println("Test 4 - Negative Numbers");
    printResult(result, expected);
  }

  private static void printResult(int[] result, int[] expected) {
    System.out.println("Expected: " + (expected == null ? "null" : Arrays.toString(expected)));
    System.out.println("Actual:   " + (result == null ? "null" : Arrays.toString(result)));
    System.out.println("----------------------------");
  }
}

---

<div
style="display: flex;
align-items: center;
justify-content: center;"
>
Happy Coding 🙂
</div>