ElbazAhmed/Data-Structures-and-Algorithms

This repository contains my solutions to various problems and my practice implementations of data structures and algorithms in Java.

Arrays - ArrayList

Informally, an array is a list of elements. These elements can be of any type: numbers, words, objects, or even other arrays. Each element in an array is accessed by its index, which starts from 0. Arrays are typically enclosed in square brackets with elements separated by commas, like this: [1, 2, 3]. In this example, the elements of the array are 1, 2, and 3.

Static Size Property

Arrays in many programming languages, including Java, have a fixed size. This means that once an array is created, its size cannot be changed. This static size property can be a limitation when the number of elements is not known in advance or if the size of the array needs to change dynamically.

int[] numbers = new int[3]; // An array of fixed size 3
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;

Solution with ArrayList

To overcome the limitation of fixed size arrays, Java provides the ArrayList class, which is part of the java.util package. ArrayList is a resizable array implementation of the List interface. It can grow and shrink as needed, providing more flexibility.

import java.util.ArrayList;
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);

Memory Allocation of an Array

When an array is created, a contiguous block of memory is allocated to hold its elements. The size of this memory block is determined by the number of elements and the type of each element. For example, an array of integers (int[]) in Java will allocate memory for the integer values based on their data type size.

int[] array = new int[5]; // Allocates memory for 5 integers

Each element in the array is stored in a contiguous memory location, which allows for efficient access using the index. However, this also means that resizing the array (increasing or decreasing its size) is not straightforward and typically requires creating a new array and copying the elements, which is why using an ArrayList can be more convenient for dynamic data structures.

Helpful Resources

An Overview of Arrays and Memory (Data Structures & Algorithms #2)
What is an Array? - Processing Tutorial
Declare, Initialize, and Use an Array - Processing Tutorial

Boyer-Moore Majority Voting Algorithm

The Boyer-Moore voting algorithm is one of the popular optimal algorithms which is used to find the majority element among the given elements that have more than N/ 2 occurrences. This works perfectly fine for finding the majority element which takes 2 traversals over the given elements, which works in O(N) time complexity and O(1) space complexity.

1. Counting Phase:

• This phase identifies a potential candidate for the majority element.
• Initialize a variable candidate to 0 and a counter count to 0.
• Traverse the array, and for each element:
  • If count is 0, update candidate with the current element and set count to 1.
  • If the current element equals candidate, increment count.
  • Otherwise, decrement count.

2. Verification Phase:

• This phase verifies if the identified candidate is indeed the majority element.
• Reset the count to 0 and traverse the array again to count the occurrences of candidate.
• If candidate appears more than ½ times (where n is the length of the array), it is the majority element.
• Else return -1.

Java Implementation

public class BoyerMooreVoting {
  public static int findMajorityElement(int[] nums) {
      // Counting Phase
      int candidate = 0;
      int count = 0;
      
      for (int num : nums) {
          if (count == 0) {
              candidate = num;
          }
          count += (num == candidate) ? 1 : -1;
      }
      
      // Verification Phase
      count = 0;
      for (int num : nums) {
          if (num == candidate) {
              count++;
          }
      }
      
      return count > nums.length / 2 ? candidate : -1;
  }
  
  public static void main(String[] args) {
      int[] nums = {2, 2, 1, 1, 1, 2, 2};
      int majorityElement = findMajorityElement(nums);
      System.out.println(majorityElement);  // Output: 2
  }

Complexity Analysis

• Time Complexity: O(n) — Each phase traverses the array once.
• Space Complexity: O(1) — The algorithm uses only a few additional variables regardless of the array size.