Array Problems

Intro

There’s many many different patterns to dealing with Arrays problems. Everything from brute force solutions that are O(n^2) to clever sorts and searches. Review Arrays

Two Sum - Easy

In which an array of numbers has two values that sum up to a given target value. The naive approach is to brute force it, but if you use a HashMap of each number and its index, you can start checking if the difference of target - numbers[i] is already in that hash map and therefore you’ve hit the second number, leading to a O(n) solution.

Best Time Buy and Sell - Easy

Iterating through an array twice but in O(n) If you need to iterate through an array twice to check for values that meet certain conditions, consider only one loop in which you check the conditions as you go through. This is done via DynamicProgramming. A a programming paradigm of sorts in which the result is found by comparing it to the previous result. Very common with problems that require recursion. Consider this simple LeetCode problem I’ve also done this in Python, just replace Infinity with None and Python enumerate function to iterate.

function maxProfit(prices: number[]): number {
   // Solution 2 - Math module, one loop -> O(n)
   let max_stonks = 0;
   let min_price = Infinity;
 
   for(let i = 0; i < prices.length; i++){
        const current: number = prices[i] - min_price;
        min_price = (min_price > prices[i]) ? prices[i] : min_price;
        max_stonks = (current > max_stonks) ? current : max_stonks;
   }
   return max_stonks;
};

Median of Two Sorted Arrays - Easy

Utilizes 3 while loops, the first is comparing elements until one of i and j indices reaches the end. The other two are for the remaining elements in the other array.

Code in Java:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums2.length + nums1.length];
        int i = 0, j = 0, k = 0;
 
        // add the smaller of the two numbers
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        // Adding the remainders to which are sorted
        while (i < nums1.length) {
            merged[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            merged[k++] = nums2[j++];
        }
 
        if (merged.length % 2 == 0) {
            int mid = merged.length / 2;
            return (double) (merged[mid] + merged[mid - 1]) / 2;
        } else {
            return merged[(merged.length / 2)];
        }
    }
}

To get a hand on it try the following example using a debugger:

MedianTwoSortedArrays clssy = new MedianTwoSortedArrays();  
int[] nums1 = {1, 3};  
int[] nums2 = {2, 4};  
System.out.println(clssy.findMedianSortedArrays(nums1, nums2));

Binary Search in Array - Easy

This one’s a classic, it does use the underlying concept of recursively searching using by comparing the middle element and checking if less or greater than target. But unlike the BST version, you’re not calling actually making a recursive call, instead you’re using two pointers.

Procedure

1. set left to 0 and right to n- 1, where n is the length of the array.
2. Set middle to be l + floor((right - left) / 2)
3. While left is less than or equal to right, check if the middle element is less than or greater than the target.
   1. If greater, then set left to middle + 1
   2. If less, then set right to middle - 1
4. If middle == target return middle
5. else return -1

 public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
 
        while (left <= right) {
            int mid = left + floor((right - left) / 2);
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
}

Setting the middle pointer

We set it to L + floor((R - L) / 2) instead of (R + L) / 2 to avoid integer overflow because in some programming languages (like C++, Java, etc.), integers have a fixed maximum size (e.g., 2³¹ - 1 for a 32-bit signed integer). If L and R are both large numbers, it might overflow and cause exceptions…

Valid Anagram - Easy

Anagram refers to a string that has the same specific characters as another AND the same count per character. Link This is my “normal” and intuitive solution, however it’s not the most efficient. it’s certainly $O(n)$ at the very least, but I don’t know for certain the time complexity of the Array.sort() function in Java, nor the toCharArray() function… These play a role in efficiency. Regardless, this is a simple solution that was penned in 5min. Code:

class Solution {
    public boolean isAnagram(String s, String t) {
       if (s.length() != t.length()) {
            return false;
        }
        
        char[] chars1 = s.toCharArray();
        char[] chars2 = t.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        for (int i = 0; i < chars1.length; i++) {
            if(chars1[i] != chars2[i]) {
                return false;
            }
        }
        return true;
    }
}

A better and way more clever solution utilizes the fact that Characters are numerically represented in UNICODE . How it works:

1. If lengths aren’t equal, return false.
2. Initialize an integer array, 26 elements.
3. Iterate through first string and use the index of the char within the alphabet and increment it.
4. Iterate through second string.
   1. If value at index is 0 then return false.
   2. Otherwise decrement, to account for differences.

Step 4 is where the comparisons happen, try it on paper with simple example if unsure what I mean. Note that these solutions end up being similar time complexity wise but the second one is more memory efficient. Code:

class Solution {
    public boolean isAnagram(String s, String t) {
       if (s.length() != t.length()) {
            return false;
        }
        
        int[] charCount = new int[26];
        for(int i = 0; i < s.length(); i++){
            charCount[s.charAt(i) - 'a'] += 1;
        }
 
        for(int i = 0; i < t.length(); i++){
            if(charCount[t.charAt(i) - 'a'] == 0){
                return false;
            }
            charCount[t.charAt(i) - 'a'] -= 1;
        }
        return true;
    }
}