davistar21

Valid Sudoku (CPP)

Problem Link

The Mission

I tackled the Valid Sudoku problem today and it was a fun challenge. The goal is to determine if a given Sudoku board is valid, meaning no row, column, or 3x3 box contains the same number more than once. It's interesting because it requires a combination of logic and algorithmic thinking to solve efficiently.

The Strategy

To solve this problem, I chose a straightforward approach: iterate through the board and keep track of the numbers we've seen so far in each row, column, and box. I used three 2D vectors, row, col, and box, to store this information. The key insight here is to use the fact that the Sudoku board is divided into 3x3 boxes, and we can calculate the index of the box for each cell using the formula (i / 3) * 3 + j / 3.

The Code

class Solution {

davistar21

Top K Frequent Elements (CPP)

The Mission

I tackled the Top K Frequent Elements problem today and it was a fun challenge. The goal is to find the top k frequent elements in an array, which sounds simple but has some interesting twists. The problem is interesting because it requires a combination of hashing and bucketing to efficiently find the top k elements.

The Strategy

I chose to use a combination of an unordered map to count the frequency of each element and a bucket array to store the elements based on their frequency. This approach allows us to efficiently find the top k elements in O(N) time complexity, where N is the number of elements in the array. The key insight here is to use the bucket array to store the elements in decreasing order of frequency, which makes it easy to find the top k elements.

The Code

davistar21

Two Sum II (Input Array is Sorted) (CPP)

Problem Link

The Mission

I tackled the Two Sum II problem today, which asked me to find two numbers in a sorted array that add up to a given target. What's interesting is that the array is already sorted, which gives us a lot of leverage to optimize our solution. The goal is to return the indices of these two numbers, and I have to say, it was a fun challenge.

The Strategy

My approach was to use a two-pointer technique. I thought, why not use the fact that the array is sorted to our advantage? We can start with two pointers, one at the beginning and one at the end of the array, and move them towards each other based on the sum of the values at these pointers. It's like a game of binary search, but instead of searching for one value, we're searching for a pair of values that add up to the target.

The Code

class Solution {

davistar21

Group Anagrams (CPP)

Problem Link

The Mission

I tackled the Group Anagrams problem on LeetCode today and it was a great exercise in creative problem-solving. The goal is to group a list of strings into anagrams, which means finding all the strings that are rearrangements of each other. What's interesting about this problem is that it requires a combination of string manipulation and hashing.

The Strategy

My approach was to use an unordered map to store the sorted version of each string as the key and the original string as the value. I chose this algorithm because it allows for efficient lookup and grouping of anagrams. The key insight here is that anagrams will always have the same characters, just in a different order, so sorting the characters in each string provides a unique identifier for each group of anagrams.

The Code

class Solution {

davistar21

Longest Common Prefix (CPP)

Problem Link

The Mission

I tackled the Longest Common Prefix problem today and it was a fun challenge. The goal is to find the common prefix among a list of strings. I mean, who doesn't love a good string manipulation problem, right? It's interesting because it requires you to think about how to efficiently compare strings and find the common ground between them.

The Strategy

My approach was to use a simple iterative method. I chose this algorithm because it's easy to understand and implement. I started by checking if the input list is empty. If it is, I return an empty string. Then, I use the first string in the list as a base and iterate over its characters. For each character, I check if it matches the corresponding character in the other strings. If I find a mismatch, I return the prefix up to that point. If I get through the entire base string without finding a mismatch, I return the entire base string as the comm

davistar21

Valid Anagram (CPP)

Problem Link

The Mission

I tackled the Valid Anagram problem on LeetCode today, and I gotta say, it was a fun challenge. The goal is to determine if two given strings are anagrams of each other. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. I've solved this problem before in TypeScript, but CPP is a different beast, and I was curious to see how I'd fare.

The Strategy

My approach was to compare the lengths of the two strings first. If they're not equal, we can immediately return false, since anagrams must have the same number of characters. Then, I created an array to count the frequency of each character in the strings. I chose this algorithm because it's simple and efficient, with a time complexity that's pretty hard to beat. As I thought to myself, "if the counts don't match, it's not an anagram". I also consi

davistar21

Maximum Subarray(CPP)

Problem Link

The Mission

I tackled the Maximum Subarray problem today and it was a blast from the past - I initially nailed it in TypeScript, but I'm glad the idea still sticks and transcends just syntax. The goal is to find the largest contiguous subarray within a one-dimensional array of numbers. It's interesting because it's a classic problem that requires a clever approach to solve efficiently.

The Strategy

I chose the Kadane's algorithm approach because it's simple yet powerful. The idea is to keep track of the maximum sum of a subarray ending at each position. If the current element is greater than the sum of the current element and the previous maximum sum, we start a new subarray. Otherwise, we extend the existing subarray. I thought to myself, "What if I just keep track of the best sum I've seen so far and the current sum?"

davistar21

Product of Array Except Self (C++)

Problem Link

The Mission

I tackled the Product of Array Except Self problem today, and I've got to say, it was a nice brain teaser. The goal is to return an array where each element is the product of all numbers in the input array except itself. No division allowed, which makes it a bit more challenging.

The Strategy

I chose to approach this problem with a two-pass strategy. I thought, why not use the output array to store the running product of all numbers to the left of each index? Then, I can make a second pass from right to left, multiplying the running product of all numbers to the right of each index with the corresponding output array element. It clicked when I realized I could do this in linear time complexity.

davistar21

Contains Duplicate (C++)

Problem Link

The Mission

I tackled the Contains Duplicate problem today and it was a great exercise in hashing. The goal was to determine if a given array of integers contains any duplicates - sounds simple, but it's actually a really useful problem to solve because it comes up in all sorts of real-world scenarios, like data processing and validation.

The Strategy

My approach was to use an unordered map to keep track of the numbers I'd seen so far. I chose this algorithm because it allows for constant time lookups, which is essential for this problem. As I iterated through the array, I'd check if each number was already in the map - if it was, I'd immediately return true. If not, I'd add it to the map and keep going. What clicked for me was realizing that I didn't need to store any extra information in the map, just the fact that the number existed.

The Code

      class Solution {

davistar21

Best Time To Buy and Sell Stock (C++)

Problem Link

The Mission

I tackled the 'Best Time To Buy and Sell Stock' problem today and it was a great refresher on how to approach these types of questions. The goal is to find the maximum possible profit from a single buy and sell of a stock, given a list of daily stock prices. What makes it interesting is that you can't sell a stock before you buy it, so the order of operations matters.

The Strategy

I chose to use a simple yet effective algorithm that keeps track of the minimum price seen so far and the maximum profit that can be achieved. As I iterate through the list of prices, I update these two values accordingly. The key insight here is to always be on the lookout for a lower price to buy at, and a higher price to sell at. I initially nailed this problem in TypeScript, but I'm glad the idea still sticks and transcends just syntax - it's all about the logic.