Day 2: Mastering Arrays and Kadane’s Algorithm

Welcome back! Today, we’ll explore arrays, one of the fundamental data structures, and tackle a classic problem using Kadane’s Algorithm. Let’s continue our journey to crack DSA with TypeScript and JavaScript.

---

Understanding Arrays in TypeScript

Arrays are used to store multiple values in a single variable. In TypeScript, you can define arrays with specific types, ensuring type safety.

Declaring Arrays

1. Number Array:

   let numbers: number[] = [1, 2, 3, 4, 5];

1. String Array:

   let fruits: string[] = ["apple", "banana", "cherry"];

1. Array of Objects:

   interface Person {
       name: string;
       age: number;
   }

   let people: Person[] = [
       { name: "Alice", age: 25 },
       { name: "Bob", age: 30 }
   ];

---

Common Array Operations

1. Traversing an Array:

   numbers.forEach(num => console.log(num));

1. Adding Elements:

   numbers.push(6);  // Adds to the end
   numbers.unshift(0);  // Adds to the beginning

1. Removing Elements:

   numbers.pop();  // Removes from the end
   numbers.shift();  // Removes from the beginning

1. Searching and Filtering:

   let found = numbers.find(num => num === 3);
   let filtered = numbers.filter(num => num > 2);

---

Problem: Maximum Sum Subarray (Kadane’s Algorithm)

Problem Statement: Given an array of integers, find the contiguous subarray with the maximum sum.

Approach:

Kadane’s Algorithm efficiently solves this problem by iterating through the array and keeping track of the maximum sum at each position.

TypeScript Implementation:

const maxSubArray = (nums: number[]): number => {
    let maxCurrent = nums[0];
    let maxGlobal = nums[0];

    for (let i = 1; i < nums.length; i++) {
        maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
        if (maxCurrent > maxGlobal) {
            maxGlobal = maxCurrent;
        }
    }

    return maxGlobal;
};

const sampleArray = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(sampleArray));  // Outputs: 6

Explanation:

1. Initialize maxCurrent and maxGlobal with the first element.
2. Iterate through the array starting from the second element.
3. Update maxCurrent to the maximum of the current element or the sum of maxCurrent and the current element.
4. Update maxGlobal if maxCurrent is greater.
5. The result is stored in maxGlobal.

---

Practice Exercise

Try solving the following problems using arrays:

1. Two Sum: Find two numbers that add up to a target sum.
2. Rotate Array: Rotate an array by k positions.
3. Merge Sorted Arrays: Merge two sorted arrays into one sorted array.

---

That’s it for Day 2! Arrays are a versatile and essential part of DSA. In the next session, we’ll dive into strings and solve problems related to string manipulation. Keep coding and stay curious!