Essential Algorithms and Data Structure Implementations

Algorithm Implementations in C#

Coin Change: Number of Ways

Calculates the number of ways to make change for amount N using given coin denominations.

• Time Complexity: O(N * C), where C is the number of coins.
• Space Complexity: O(N).

static long GetNumberOfWays(long N, long[] Coins)
{
    long[] ways = new long[(int)N + 1];
    ways[0] = 1;
    for (int i = 0; i < Coins.Length; i++)
    {
        for (int j = 0; j < ways.Length; j++)
        {
            if (Coins[i] <= j)
            {
                ways[j] = ways[j] + ways[(int)(j - Coins[i])];
            }
        }
    }
    return ways[(int)N];
}

Coin Change: Minimum Number of Coins

Determines the minimum number of coins needed to make change for a given amount.

• Time Complexity: O(amount * n), where n is the number of coins.
• Space Complexity: O(amount).

static int MinCoins(int[] coins, int amount)
{
    int[] dp = new int[amount + 1];
    for (int i = 1; i <= amount; i++)
        dp[i] = int.MaxValue;

    dp[0] = 0;

    for (int i = 1; i <= amount; i++)
    {
        foreach (int coin in coins)
        {
            if (i - coin >= 0 && dp[i - coin] != int.MaxValue)
            {
                dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == int.MaxValue ? -1 : dp[amount];
}

Roman Numeral to Decimal Conversion

Converts a Roman numeral string to its decimal (integer) value.

• Time Complexity: O(n), where n is the length of the string.
• Space Complexity: O(1).

static int RomanToDecimal(string s)
{
    Dictionary romanMap = new Dictionary
    {
        {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
        {'C', 100}, {'D', 500}, {'M', 1000}
    };
    int res = 0;
    for (int i = 0; i < s.Length; i++)
    {
        if (i + 1 < s.Length && romanMap[s[i]] < romanMap[s[i + 1]])
        {
            res += romanMap[s[i + 1]] - romanMap[s[i]];
            i++;
        }
        else
        {
            res += romanMap[s[i]];
        }
    }
    return res;
}

Fibonacci Number (Recursive)

Calculates the $n^{th}$ Fibonacci number using recursion.

• Time Complexity: O(2^n).
• Space Complexity: O(n) (due to the call stack).

private static int Fibonacci(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    var response = Fibonacci(n - 1) + Fibonacci(n - 2);
    return response;
}

Merge Two Sorted Arrays

Merges two sorted arrays into a single sorted array.

• Time Complexity: O(n1 + n2).
• Space Complexity: O(n1 + n2).

private static int[] MergeAndSortTwoSortedArrays(int[] arr1, int[] arr2)
{
    int n1 = arr1.Length; int n2 = arr2.Length;
    var mergedArray = new int[n1 + n2];
    int i = 0, j = 0, k = 0;
    while (i < n1 && j < n2)
    {
        if (arr1[i] <= arr2[j])
        {
            mergedArray[k++] = arr1[i++];
        }
        else
        {
            mergedArray[k++] = arr2[j++];
        }
    }
    while (i < n1)
    {
        mergedArray[k++] = arr1[i++];
    }
    while (j < n2)
    {
        mergedArray[k++] = arr2[j++];
    }
    return mergedArray;
}

Check for Anagrams

Checks if two strings are anagrams of each other (case-insensitive).

• Time Complexity: O(n).
• Space Complexity: O(1) (assuming ASCII character set).

private static bool AreAnagrams(string str1, string str2)
{
    if (str1.Length != str2.Length)
        return false;
    int[] counts = new int[256]; // assuming ASCII
    for (int i = 0; i < str1.Length; i++)
    {
        char c1 = char.ToLower(str1[i]);
        char c2 = char.ToLower(str2[i]);
        counts[c1]++;
        counts[c2]--;
    }
    for (int i = 0; i < counts.Length; i++)
    {
        if (counts[i] != 0)
            return false;
    }
    return true;
}

Longest Substring Without Repeating Characters

Finds the length of the longest substring without repeating characters.

• Time Complexity: O(n).
• Space Complexity: O(1) (assuming ASCII character set).

private static int LongestNonRepeatingSubstring(string s)
{
    int maxLen = 0;
    int start = 0;
    int[] lastIndex = new int[256]; // ASCII
    for (int i = 0; i < 256; i++) lastIndex[i] = -1;
    for (int end = 0; end < s.Length; end++)
    {
        char c = s[end];
        if (lastIndex[c] >= start)
        {
            start = lastIndex[c] + 1;
        }
        lastIndex[c] = end;
        int len = end - start + 1;
        if (len > maxLen)
            maxLen = len;
    }
    return maxLen;
}

Longest Palindromic Substring

Finds the longest palindromic substring within a given string.

• Time Complexity: O(n^2).
• Space Complexity: O(1).

public static string LongestPalindrome(string s)
{
    if (s == null || s.Length < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.Length; i++)
    {
        int len1 = ExpandAroundCenter(s, i, i);
        int len2 = ExpandAroundCenter(s, i, i + 1);
        int len = Math.Max(len1, len2);
        if (len > end - start)
        {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.Substring(start, end - start + 1);
}

private static int ExpandAroundCenter(string s, int left, int right)
{
    // Helper for LongestPalindrome
    // Time: O(n), Space: O(1)
    int L = left, R = right;
    while (L >= 0 && R < s.Length && s[L] == s[R]) { L--; R++; }
    return R - L - 1;
}

Container With Most Water (Maximum Area)

Finds the maximum area that can be contained between two vertical lines.

• Time Complexity: O(n).
• Space Complexity: O(1).

private static int MaxArea(int[] height)
{
    int left = 0; int right = height.Length - 1; int maxArea = 0;
    while (left < right)
    {
        int area = Math.Min(height[left], height[right]) * (right - left);
        maxArea = Math.Max(maxArea, area);
        if (height[left] < height[right])
            left++;
        else
            right--;
    }
    return maxArea;
}

Trapping Rain Water

Calculates the total amount of rainwater that can be trapped.

• Time Complexity: O(n).
• Space Complexity: O(1).

private static int Trap(int[] height)
{
    int left = 0, right = height.Length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right)
    {
        if (height[left] < height[right])
        {
            leftMax = Math.Max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        }
        else
        {
            rightMax = Math.Max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

Daily Temperatures

Returns how many days you have to wait after each day to get a warmer temperature (using a monotonic stack).

• Time Complexity: O(n).
• Space Complexity: O(n).

private static int[] DailyTemperatures(int[] temperatures)
{
    int n = temperatures.Length;
    int[] answer = new int[n];
    Stack stack = new Stack(); // stores indices
    for (int i = 0; i < n; i++)
    {
        while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()])
        {
            int prevIndex = stack.Pop();
            answer[prevIndex] = i - prevIndex;
        }
        stack.Push(i);
    }
    return answer;
}

All Unique String Combinations (Subsets)

Generates all unique string combinations (subsets) without repeating characters from the input string.

• Time Complexity: O(2^n * n).
• Space Complexity: O(2^n * n).

private static List<string> AllCombinationsNoRepeat(string s)
{
    var result = new List<string>();
    var sb = new System.Text.StringBuilder();
    void Backtrack(int start)
    {
        if (sb.Length > 0)
            result.Add(sb.ToString());
        for (int i = start; i < s.Length; i++)
        {
            if (sb.ToString().Contains(s[i])) continue;
            sb.Append(s[i]);
            Backtrack(i + 1);
            sb.Length--; // backtrack
        }
    }
    Backtrack(0);
    return result;
}