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 TypeS…


This content originally appeared on DEV Community and was authored by Rohit Nair

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!


This content originally appeared on DEV Community and was authored by Rohit Nair


Print Share Comment Cite Upload Translate Updates
APA

Rohit Nair | Sciencx (2025-01-08T02:30:00+00:00) Day 2: Mastering Arrays and Kadane’s Algorithm. Retrieved from https://www.scien.cx/2025/01/08/day-2-mastering-arrays-and-kadanes-algorithm/

MLA
" » Day 2: Mastering Arrays and Kadane’s Algorithm." Rohit Nair | Sciencx - Wednesday January 8, 2025, https://www.scien.cx/2025/01/08/day-2-mastering-arrays-and-kadanes-algorithm/
HARVARD
Rohit Nair | Sciencx Wednesday January 8, 2025 » Day 2: Mastering Arrays and Kadane’s Algorithm., viewed ,<https://www.scien.cx/2025/01/08/day-2-mastering-arrays-and-kadanes-algorithm/>
VANCOUVER
Rohit Nair | Sciencx - » Day 2: Mastering Arrays and Kadane’s Algorithm. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/01/08/day-2-mastering-arrays-and-kadanes-algorithm/
CHICAGO
" » Day 2: Mastering Arrays and Kadane’s Algorithm." Rohit Nair | Sciencx - Accessed . https://www.scien.cx/2025/01/08/day-2-mastering-arrays-and-kadanes-algorithm/
IEEE
" » Day 2: Mastering Arrays and Kadane’s Algorithm." Rohit Nair | Sciencx [Online]. Available: https://www.scien.cx/2025/01/08/day-2-mastering-arrays-and-kadanes-algorithm/. [Accessed: ]
rf:citation
» Day 2: Mastering Arrays and Kadane’s Algorithm | Rohit Nair | Sciencx | https://www.scien.cx/2025/01/08/day-2-mastering-arrays-and-kadanes-algorithm/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts