Dealing with Array & Hashing Problems: Essential Tips and Tricks: Part 1

In this article, we will explore arrays and hashing problems with the top 5 famous challenges. If you've ever been frustrated by dynamic arrays or hashing problems on platforms like LeetCode, don't worry! After reading this article, you'll master these concepts effortlessly. Whether you're a beginner struggling to understand these basics or an expert looking for a quick refresher, this article has you covered.

Arrays are fundamental data structures used in programming to store collections of items of the same type. Think of an array as a sequential collection of elements (or items) that are stored in contiguous memory locations. Each element in an array is accessed by its index, which represents its position in the array. Arrays are widely used because they allow efficient access to elements using their indices, making it easy to retrieve, modify, and manipulate data stored in them.

Key characteristics of arrays include:

• Fixed Size: Arrays have a fixed size determined at the time of declaration.

• Sequential Storage: Elements are stored one after another in memory.

• Random Access: Elements can be accessed directly by their index.

Arrays can store primitive data types (like integers, floats, characters) as well as objects (like instances of classes or structures). They are versatile and form the basis for more complex data structures and algorithms in computer science and programming.

Dynamic arrays, often referred to as resizable arrays or vectors in some programming languages, are arrays that can grow or shrink in size dynamically at runtime. Unlike static arrays, where the size is fixed and determined at compile time, dynamic arrays allow for flexibility in managing memory allocation based on the actual needs of the program.

Example in Python:

In Python, lists are dynamic arrays by default. Here's an example of how you can use a list (dynamic array) to store integers:

# Creating a dynamic array (list) in Python
dynamic_array = []

# Appending elements to the dynamic array
dynamic_array.append(10)
dynamic_array.append(20)
dynamic_array.append(30)

# Printing the dynamic array
print("Dynamic Array:", dynamic_array)

# Modifying elements
dynamic_array[1] = 50

# Printing the modified dynamic array
print("Modified Dynamic Array:", dynamic_array)

In this Python example:

• dynamic_array starts empty and grows dynamically as elements are appended (append() method).

• Elements can be accessed and modified using indices just like in a static array.

Example in C++:

In C++, dynamic arrays are typically managed using pointers and memory allocation functions like new and delete. Alternatively, the std::vector class provides a convenient and safe way to work with dynamic arrays:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // Creating a dynamic array (vector) in C++
    vector<int> dynamic_array;

    // Appending elements to the dynamic array
    dynamic_array.push_back(10);
    dynamic_array.push_back(20);
    dynamic_array.push_back(30);

    // Printing the dynamic array
    cout << "Dynamic Array:";
    for (int i = 0; i < dynamic_array.size(); ++i) {
        cout << " " << dynamic_array[i];
    }
    cout << endl;

    // Modifying elements
    dynamic_array[1] = 50;

    // Printing the modified dynamic array
    cout << "Modified Dynamic Array:";
    for (int i = 0; i < dynamic_array.size(); ++i) {
        cout << " " << dynamic_array[i];
    }
    cout << endl;

    return 0;
}

In this C++ example:

• vector<int> dynamic_array; creates a dynamic array (vector) that initially has a size of 0.

• Elements are added using push_back() method.

• Elements are accessed and modified using indices (dynamic_array[i]).

• The std::vector class manages memory dynamically and provides safety features like bounds checking.

Both examples demonstrate the flexibility and convenience of dynamic arrays, which can grow and shrink based on program requirements, unlike static arrays whose size is fixed.

Certainly! Here are two basic problems involving arrays from LeetCode and GeeksforGeeks, along with explanations and code solutions:

Problem 1: Remove Duplicates from Sorted Array

Problem Statement: Given a sorted array nums, remove the duplicates in-place such that each element appears only once and return the new length.

Example:

Input: nums = [1, 1, 2]
Output: 2 (nums becomes [1, 2])

Approach:

• Use two pointers: one (i) to iterate through the array and another (j) to track the position where the next non-duplicate element should be placed.

• As you iterate through the array with i, compare nums[i] with nums[j-1] (last placed unique element).

• If nums[i] is different from nums[j-1], copy nums[i] to nums[j] and increment j.

• The length of the resulting array (j) will give the number of unique elements.

Code:

def removeDuplicates(nums):
    if len(nums) == 0:
        return 0

    j = 1  # pointer for the position to place the next unique element
    for i in range(1, len(nums)):
        if nums[i] != nums[j - 1]:
            nums[j] = nums[i]
            j += 1

    return j

# Example usage:
nums = [1, 1, 2]
new_length = removeDuplicates(nums)
print("New Length:", new_length)
print("Modified Array:", nums[:new_length])

Explanation:

• The function removeDuplicates modifies the array nums in-place.

• It initializes j to 1 since the first element is always unique.

• It iterates through the array with i, comparing each element with the last placed unique element (nums[j-1]).

• If a different element is found (nums[i] != nums[j-1]), it is placed in the next position (nums[j]) and j is incremented.

• Finally, j gives the length of the modified array with unique elements, and nums[:j] provides the array with unique elements.

Problem 2: Find the Maximum Product of Two Integers in an Array

Problem Statement: Given an integer array nums, find two integers in the array which produce the maximum product and return the product.

Example:

Input: nums = [3, 5, 2, 6]
Output: 30 (Product of 5 and 6)

Approach:

• Track the maximum and second maximum elements in a single pass through the array (max1 and max2).

• Also, track the minimum and second minimum elements (min1 and min2) to handle negative numbers that might produce larger positive products.

• Update these variables as you iterate through the array.

• The maximum product can be either max1 * max2 or min1 * min2.

Code:

def maxProduct(nums):
    if len(nums) < 2:
        return 0

    max1 = max2 = float('-inf')
    min1 = min2 = float('inf')

    for num in nums:
        if num > max1:
            max2 = max1
            max1 = num
        elif num > max2:
            max2 = num

        if num < min1:
            min2 = min1
            min1 = num
        elif num < min2:
            min2 = num

    return max(max1 * max2, min1 * min2)

# Example usage:
nums = [3, 5, 2, 6]
max_product = maxProduct(nums)
print("Maximum Product:", max_product)

Explanation:

• The function maxProduct initializes max1, max2, min1, and min2 to handle the largest and smallest elements encountered.

• It iterates through the array, updating max1, max2, min1, and min2 accordingly.

• Finally, it computes and returns the maximum of max1 * max2 and min1 * min2, which gives the maximum product of two integers in the array.

These problems illustrate basic array manipulation and computation tasks that are foundational in programming interviews and competitive programming. They emphasize efficient use of array traversal and manipulation techniques.

Now that we know how to approach basic array problems, we can move on to some intermediate-level concepts. You will see these in the upcoming blog. Until then, keep hustling!