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 BinarySearch 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

set left to 0 and right to n- 1, where n is the length of the array.
Set middle to be l + floor((right - left) / 2)
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
If middle == target return middle
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:

If lengths aren’t equal, return false.
Initialize an integer array, 26 elements.
Iterate through first string and use the index of the char within the alphabet and increment it.
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;
    }
}

First Bad Version - Easy

This one’s another spin on BinarySearch. Although the input is an integer n representing the number of versions, such that $1 <= v ers i o n <= n$ . We’re tasked with finding the first bad version, given an API (function) that determines if a version’s bad or not.

Breakdown

Set start to 1 and end to n.
While start < end, init mid value.
check isBad(mid):
1. If true, set end = mid
2. else start = mid
return start This one differs than regular Binary Search because you’re trying to find the first bad version, which means moving the start till it hits the first.

Code:

public int firstBadVersion(int n) {  
    int start = 1;  
    int end = n;  
    while(start < end){  
        int mid =  start + ((end - start) / 2);  
        if(isBadVersion(mid)){  
            end = mid;  
        } else {  
            start = mid + 1;  
        }  
    }  
    return start;  
}

Ransom Note - Easy

Another simple but faster solution compared to the hashmap solution.

Breakdown

Init a 26 integer array, to represent our alphabet’s count… Very similar to Valid Anagram above!
Iterate through the magazine and count.
Iterate through the note and check if count’s greater than or equal to one.
- Decrement if yes
- return false otherwise // I have both ways of iterating through them using for loops for sake of flavor and diversity... Code:

public boolean canConstruct(String note, String magazine) {  
    if (magazine.length() < note.length()) return false;  
  
    int[] charCount = new int[26];  
    for (char c : magazine.toCharArray()) {  
        charCount[c - 'a']++;  
    }  
  
    for (int i = 0; i < note.length(); i++) {  
        if (charCount[note.charAt(i) - 'a'] >= 1) {  
            charCount[note.charAt(i) - 'a']--;  
        }  
        else return false;  
    }  
    return true;  
}

Majority Element - Easy

You’re given an array of randomized integers, often repeating more than once. And you’re asked to return the majority element, i.e. the element that appears more than $f l oor (n /2)$ times in the array. Where n is the number of elements in the array such that $1 <= n <= 5 * 1 0^{4}$

My Solution

My first intuition was, this can be solved using a HashMap. That will end up being a time and space solution because of traversing the hashmap’s key-value pairs until the majority is found. Cool, but we’re better than that, only a bit…

Breakdown

Sort the array of integers, use built-in function as it’s optimized for a simple task like this.
Init two variables, the majority and its count.
Iterate once through the sorted array while checking the conditions. Code:

def majorityElement(self, nums: List[int]) -> int:
	if len(nums) == 1:
		return nums[0]
 
	sorted_nums = sorted(nums)
	majority = sorted_nums[0]
	count = 0
	for i in range(0, len(nums)):
		if sorted_nums[i] == majority:
			count += 1
		elif sorted_nums[i] != majority and count < len(nums) / 2:
			majority = sorted_nums[i]
			count = 1
	
	return majority

This is a a $O (n)$ time and $O (1)$ space solution.

Boyer-Moore Voting Algorithm

Now, for a smarter solution.

Breakdown

Initialize a majority variable and a count variable.
Traverse the array once:
→ If count is 0, set the majority to the current element and set count to one.
→ If the current element equals the majority, increment count.
→ If the current element differs from the majority, decrement count.
Traverse the array again to count the appearances of majority.
If the majority’s count is greater than $n /2$ , return the majority as the majority element. Code:

def majority_element_boyer_moore(self, nums):  
    majority = -1  
    count = 0  
    for a in nums:  
        if count == 0:  
            majority = a  
        if a == majority:  
            count += 1  
        else:  
            count -= 1  
    return majority

For a thorough explanation (you need to draw it out) check this video by Greg Hogg

Abdu's Garden

Explorer

Array Problems

Intro

Two Sum - Easy

Best Time Buy and Sell - Easy

Median of Two Sorted Arrays - Easy

Binary Search in Array - Easy

Procedure

Valid Anagram - Easy

First Bad Version - Easy

Breakdown

Ransom Note - Easy

Breakdown

Majority Element - Easy

My Solution

Breakdown

Boyer-Moore Voting Algorithm

Breakdown

Graph View

Table of Contents

Backlinks