Array / String

Table of Contents

• 13. Roman to Integer
• 14. Longest Common Prefix
• 26. Remove Duplicates from Sorted Array
• 27. Remove Element
• 28. Find the Index of the First Occurrence in a String
• 58. Length of Last Word
• 88. Merge Sorted Array
• 121. Best Time to Buy and Sell Stock
• 169. Majority Element
• 2043. Simple Bank System
• 2672. Number of Adjacent Elements With the Same Color

13. Roman to Integer

• LeetCode Link: Roman to Integer
• Difficulty: Easy
• Topic(s): Hash Table, String, Math
• Company: Google

🧠 Problem Statement

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

🧩 Approach

1. Create a mapping of Roman numeral symbols to their integer values.
2. Initialize a result variable to 0.
3. Iterate through the string:
   • If the current symbol is less than the next symbol, subtract its value from the result.
   • Otherwise, add its value to the result.
4. Return the result.

💡 Solution

from typing import Dict

class Solution:
    def romanToInt(self, s: str) -> int:
        """
        Convert a Roman numeral to an integer.

        Args:
            s (str): The Roman numeral string.

        Returns:
            int: The integer representation of the Roman numeral.
        """
        romans: Dict[str, int] = {
                "I": 1,
                "V": 5,
                "X": 10,
                "L": 50,
                "C": 100,
                "D": 500,
                "M": 1000
        }
        res: int = 0
        for i in range(len(s)):
            if i + 1 < len(s) and romans[s[i]] < romans[s[i + 1]]:
                res -= romans[s[i]]
            else:
                res += romans[s[i]]
        return res

🧮 Complexity Analysis

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

14. Longest Common Prefix

• LeetCode Link: Longest Common Prefix
• Difficulty: Easy
• Topic(s): String, Trie
• Company: Meta

🧠 Problem Statement

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

🧩 Approach

1. Initialize the result as an empty string.
2. Iterate through the characters of the first string.
3. For each character, check if it matches the corresponding character in all other strings.
4. If a mismatch is found or if the end of any string is reached, return the result.
5. If all characters match, append the character to the result.
6. Return the result after checking all characters of the first string.

💡 Solution

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        """
        Find the longest common prefix among an array of strings.

        Args:
            strs (List[str]): The list of strings.

        Returns:
            str: The longest common prefix.
        """
        res: str = ""
        for i in range(len(strs[0])):
            for s in strs:
                if i == len(s) or s[i] != strs[0][i]:
                    return res
            res += strs[0][i]
        return res

🧮 Complexity Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(1)

26. Remove Duplicates from Sorted Array

• LeetCode Link: Remove Duplicates from Sorted Array
• Difficulty: Easy
• Topic(s): Array, Two Pointers
• Company: Microsoft

🧠 Problem Statement

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

🧩 Approach

Use the two-pointer technique:

• i: slow pointer, tracks the position of the last unique element.
• j: fast pointer, scans the array.

Steps:

1. Initialize i = 0.
2. Iterate j from 1 to end of array.
3. If nums[j] != nums[i], it’s a new unique element:
   • Increment i
   • Copy nums[j] to nums[i]
4. After the loop, the first i + 1 elements are the unique values.

💡 Solution

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        """
        Remove duplicates from a sorted array in-place and return the new length.

        Args:
            nums (List[int]): The input sorted array.

        Returns:
            int: The new length of the array after removing duplicates.
        """
        i: int = 0

        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]

        return i + 1

🧮 Complexity Analysis

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

27. Remove Element

• LeetCode Link: Remove Element
• Difficulty: Easy
• Topic(s): Array, Two Pointers
• Company: Apple

🧠 Problem Statement

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums that are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

🧩 Approach

Use the two-pointer technique:

• One pointer (i) scans every element.
• Another pointer (k) keeps track of the position where the next valid (non-val) element should be placed.

Steps:

1. Iterate through the array.
2. If the current element is not equal to val, place it at index k and increment k.
3. After the loop, k will represent the new length of the array with val removed.

💡 Solution

from typing import List

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        """
        Remove all occurrences of `val` in `nums` in-place and return the new length.

        Args:
            nums (List[int]): The input array.
            val (int): The value to be removed.

        Returns:
            int: The new length of the array after removal.
        """
        k: int = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1
        return k

🧮 Complexity Analysis

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

28. Find the Index of the First Occurrence in a String

• LeetCode Link: Find the Index of the First Occurrence in a String
• Difficulty: Easy
• Topic(s): Two Pointers, String, String Matching
• Company: Google

🧠 Problem Statement

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

🧩 Approach

Use a simple sliding window approach:

1. Iterate through haystack with a window of size equal to the length of needle.
2. For each position, check if the substring matches needle.
3. If a match is found, return the starting index.
4. If no match is found after checking all possible positions, return -1.

💡 Solution

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        """
        Find the index of the first occurrence of `needle` in `haystack`.

        Args:
            haystack (str): The string to search in.
            needle (str): The substring to search for.

        Returns:
            int: The index of the first occurrence of `needle` in `haystack`, or -1 if not found.
        """
        for i in range(len(haystack) + 1 - len(needle)):
            if haystack[i: i + len(needle)] == needle:
                return i
        return -1

🧮 Complexity Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(1)

58. Length of Last Word

• LeetCode Link: Length of Last Word
• Difficulty: Easy
• Topic(s): String, String Manipulation
• Company: Amazon

🧠 Problem Statement

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

Example 1:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2:

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Example 3:

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

🧩 Approach

1. Split the string s into words using the split() method, which automatically handles multiple spaces.
2. Return the length of the last word in the list of words.

💡 Solution

from typing import List

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        """
        Calculate the length of the last word in a string.

        Args:
            s (str): The input string.

        Returns:
            int: The length of the last word.
        """
        words: List[str] = s.split()
        return len(words[-1])

🧮 Complexity Analysis

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

88. Merge Sorted Array

• LeetCode Link: Merge Sorted Array
• Difficulty: Easy
• Topic(s): Array, Two Pointers, Sorting
• Company: Meta

🧠 Problem Statement

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

🧩 Approach

Use three pointers:

• midx points to the last valid element in nums1 (m - 1)
• nidx points to the last element in nums2 (n - 1)
• right points to the last index in nums1 (m + n - 1)

Compare elements from the back and place the larger one at index right. Decrement pointers accordingly.

Repeat until nidx reaches 0 (no need to worry about midx, since the rest are already in place).

💡 Solution

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Merge two sorted arrays `nums1` and `nums2` into `nums1` in-place.

        Args:
            nums1 (List[int]): The first sorted array with enough space to hold the elements of `nums2`.
            m (int): The number of elements in `nums1`.
            nums2 (List[int]): The second sorted array.
            n (int): The number of elements in `nums2`.

        Returns:
            None: The result is stored in `nums1`.
        """
        midx: int = m - 1
        nidx: int = n - 1
        right: int = m + n - 1

        while nidx >= 0:
            if midx >= 0 and nums1[midx] > nums2[nidx]:
                nums1[right] = nums1[midx]
                midx -= 1
            else:
                nums1[right] = nums2[nidx]
                nidx -= 1

            right -= 1

🧮 Complexity Analysis

• Time Complexity: O(m + n)
• Space Complexity: O(1)

121. Best Time to Buy and Sell Stock

• LeetCode Link: Best Time to Buy and Sell Stock
• Difficulty: Easy
• Topic(s): Array, Dynamic Programming
• Company: Amazon

🧠 Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

🧩 Approach

Dynamic programming approach:

1. Initialize profit to 0 and lowest to the first price.

2. Iterate through the prices:

   • For each price, calculate the potential profit by subtracting lowest from the current price.
   • Update profit if the calculated profit is greater than the current profit.
   • Update lowest to be the minimum of the current price and lowest.

3. Return the profit.

This approach ensures that we always consider the lowest price seen so far, allowing us to calculate the maximum profit efficiently.

💡 Solution

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """
        Calculate the maximum profit from a single buy and sell transaction.

        Args:
            prices (List[int]): The list of stock prices.

        Returns:
            int: The maximum profit achievable, or 0 if no profit can be made.
        """
        profit: int = 0
        lowest: int = prices[0]

        for price in prices:
            profit = max(profit, price - lowest)
            lowest = min(lowest, price)
        return profit

🧮 Complexity Analysis

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

169. Majority Element

• LeetCode Link: Majority Element
• Difficulty: Easy
• Topic(s): Array, Hash Table, Divide and Conquer, Counting
• Company: Apple

🧠 Problem Statement

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

🧩 Approach

Boyer-Moore Voting Algorithm:

1. Initialize a count = 0 and candidate = None.
2. Iterate through the array:
   • If count == 0, set candidate = current element
   • If current element == candidate, increment count
   • Else, decrement count
3. At the end, candidate is the majority element.

This works because the majority element appears more than all others combined.

💡 Solution

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        """
        Find the majority element in an array using Boyer-Moore Voting Algorithm.

        Args:
            nums (List[int]): The input array.

        Returns:
            int: The majority element.
        """
        count: int = 0
        candidate: int = 0

        for num in nums:
            if count == 0:
                candidate = num

            if num == candidate:
                count += 1
            else:
                count -= 1

        return candidate

🧮 Complexity Analysis

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

2043. Simple Bank System

• LeetCode Link: Simple Bank System
• Difficulty: Medium
• Topic(s): Design, Array
• Company: Capital One

🧠 Problem Statement

You have been tasked with writing a program for a popular bank that will automate all its incoming transactions (transfer, deposit, and withdraw). The bank has n accounts numbered from 1 to n. The initial balance of each account is stored in a 0-indexed integer array balance, with the (i + 1)th account having an initial balance of balance[i].

Execute all the valid transactions. A transaction is valid if:

• The given account number(s) are between 1 and n, and
• The amount of money withdrawn or transferred from is less than or equal to the balance of the account.

Implement the Bank class:

• Bank(long[] balance) Initializes the object with the 0-indexed integer array balance.
• boolean transfer(int account1, int account2, long money) Transfers money dollars from the account numbered account1 to the account numbered account2. Return true if the transaction was successful, false otherwise.
• boolean deposit(int account, long money) Deposit money dollars into the account numbered account. Return true if the transaction was successful, false otherwise.
• boolean withdraw(int account, long money) Withdraw money dollars from the account numbered account. Return true if the transaction was successful, false otherwise.

Example 1:

Input
["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"]
[[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]]
Output
[null, true, true, true, false, false]

Explanation
Bank bank = new Bank([10, 100, 20, 50, 30]);
bank.withdraw(3, 10);    // return true, account 3 has a balance of $20, so it is valid to withdraw $10.
                         // Account 3 has $20 - $10 = $10.
bank.transfer(5, 1, 20); // return true, account 5 has a balance of $30, so it is valid to transfer $20.
                         // Account 5 has $30 - $20 = $10, and account 1 has $10 + $20 = $30.
bank.deposit(5, 20);     // return true, it is valid to deposit $20 to account 5.
                         // Account 5 has $10 + $20 = $30.
bank.transfer(3, 4, 15); // return false, the current balance of account 3 is $10,
                         // so it is invalid to transfer $15 from it.
bank.withdraw(10, 50);   // return false, it is invalid because account 10 does not exist.

🧩 Approach

1. Initialize the Bank class with the given balances.
2. Implement the transfer method to check for valid accounts and sufficient balance before transferring money.
3. Implement the deposit method to add money to the specified account if valid.
4. Implement the withdraw method to deduct money from the specified account if valid.

💡 Solution

from typing import List

class Bank:

    def __init__(self, balance: List[int]):
        """
        Initialize the Bank with the given balances.

        Args:
            balance (List[int]): The initial balances of the accounts.
        """
        self.balance: List[int] = balance

    def transfer(self, account1: int, account2: int, money: int) -> bool:
        """
        Transfer money from account1 to account2 if valid.

        Args:
            account1 (int): The account number to transfer money from.
            account2 (int): The account number to transfer money to.
            money (int): The amount of money to transfer.

        Returns:
            bool: True if the transfer was successful, False otherwise.
        """
        if (
            account1 > len(self.balance)
            or account2 > len(self.balance)
            or self.balance[account1 - 1] < money
        ):
            return False
        self.balance[account1 - 1] -= money
        self.balance[account2 - 1] += money
        return True

    def deposit(self, account: int, money: int) -> bool:
        """
        Deposit money into the specified account if valid.

        Args:
            account (int): The account number to deposit money into.
            money (int): The amount of money to deposit.

        Returns:
            bool: True if the deposit was successful, False otherwise.
        """
        if account > len(self.balance):
            return False

        self.balance[account - 1] += money
        return True

    def withdraw(self, account: int, money: int) -> bool:
        """
        Withdraw money from the specified account if valid.

        Args:
            account (int): The account number to withdraw money from.
            money (int): The amount of money to withdraw.

        Returns:
            bool: True if the withdrawal was successful, False otherwise.
        """
        if account > len(self.balance) or self.balance[account - 1] < money:
            return False

        self.balance[account - 1] -= money
        return True

🧮 Complexity Analysis

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

2672. Number of Adjacent Elements With the Same Color

• LeetCode Link: Number of Adjacent Elements With the Same Color
• Difficulty: Easy
• Topic(s): Array, Simulation
• Company: Capital One

🧠 Problem Statement

You are given an integer n representing an array colors of length n where all elements are set to 0’s meaning uncolored. You are also given a 2D integer array queries where queries[i] = [indexi, colori]. For the ith query:

Set colors[indexi] to colori. Count the number of adjacent pairs in colors which have the same color (regardless of colori). Return an array answer of the same length as queries where answer[i] is the answer to the ith query.

Example 1:

Input: n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

Output: [0,1,1,0,2]

Explanation:

Initially array colors = [0,0,0,0], where 0 denotes uncolored elements of the array.
After the 1st query colors = [2,0,0,0]. The count of adjacent pairs with the same color is 0.
After the 2nd query colors = [2,2,0,0]. The count of adjacent pairs with the same color is 1.
After the 3rd query colors = [2,2,0,1]. The count of adjacent pairs with the same color is 1.
After the 4th query colors = [2,1,0,1]. The count of adjacent pairs with the same color is 0.
After the 5th query colors = [2,1,1,1]. The count of adjacent pairs with the same color is 2.

Example 2:

Input: n = 1, queries = [[0,100000]]

Output: [0]

Explanation:

After the 1st query colors = [100000]. The count of adjacent pairs with the same color is 0.

🧩 Approach

1. Initialize a count variable to keep track of adjacent pairs with the same color.
2. Create an array nums of size n initialized to 0 to represent uncolored elements.
3. For each query:
   • Check the previous and next elements of the index being colored.
   • If the current element is already colored and matches the previous or next element, decrement the count.
   • Update the color of the current index.
   • If the new color matches the previous or next element, increment the count.
4. Append the current count to the result list after each query.

💡 Solution

from typing import List

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        count: int = 0
        res: List[int] = []
        nums: List[int] = [0 for _ in range(n)]

        for idx, color in queries:
            prev: int = nums[idx - 1] if idx > 0 else 0
            nxt: int = nums[idx + 1] if idx < n - 1 else 0

            if nums[idx] and nums[idx] == prev:
                count -= 1

            if nums[idx] and nums[idx] == nxt:
                count -= 1

            nums[idx] = color

            if nums[idx] and nums[idx] == prev:
                count += 1

            if nums[idx] and nums[idx] == nxt:
                count += 1

            res.append(count)

        return res

🧮 Complexity Analysis

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