Array and String Manipulation

Introduction

Array and string manipulation problems are fundamental in programming interviews and real-world applications. These problems test your ability to work with data structures efficiently, handle edge cases, and implement algorithms that operate in-place or with minimal space complexity.

In this article, we’ll explore various array and string manipulation techniques through practical LeetCode problems, providing clean, well-explained solutions in both C# and Python.

Common Techniques

Two Pointers

Using two pointers to traverse arrays or strings, often reducing time complexity from O(n²) to O(n).

In-Place Operations

Modifying arrays or strings without using extra space, often using swapping or overwriting.

String Parsing

Processing strings character by character, handling whitespace, signs, and edge cases.

Pattern Recognition

Identifying mathematical patterns or cycles in problems to optimize solutions.

Problem 1: Move Zeroes

Problem Statement

Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Input: nums = [0]
Output: [0]

Understanding the Problem

We need to rearrange the array so all zeros are at the end, but non-zero elements maintain their original relative order. This must be done in-place.

Solution Strategy

Two Pointers Approach:

1. Use pos pointer to track where the next non-zero element should be placed
2. Iterate through array with i
3. When we find a non-zero element:
   • If i != pos, swap elements (or copy and zero out)
   • Increment pos
4. All zeros naturally end up at the end

C# Solution

public class Solution 
{
    public void MoveZeroes(int[] nums) 
    {
        // pos tracks where next non-zero element should be placed
        int pos = 0;
        
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] != 0)
            {
                // Only swap if positions are different
                if (i != pos)
                {
                    nums[pos] = nums[i];
                    nums[i] = 0;
                }
                pos++;
            }
        }
    }
}

Python 3 Solution

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        pos = 0
        
        for i in range(len(nums)):
            if nums[i] != 0:
                if i != pos:
                    nums[pos] = nums[i]
                    nums[i] = 0
                pos += 1

Complexity Analysis

• Time Complexity: O(n) where n is the length of nums
• Space Complexity: O(1) – only using constant extra space

Key Insight

The pos pointer always points to the position where the next non-zero element should go. By swapping (or copying and zeroing), we maintain the relative order while moving zeros to the end.

Problem 2: Is Subsequence

Problem Statement

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.

Example

Input: s = "abc", t = "ahbgdc"
Output: true

Input: s = "axc", t = "ahbgdc"
Output: false

Understanding the Problem

We need to check if all characters of s appear in t in the same order (but not necessarily consecutively).

Solution Strategy

Two Pointers Approach:

1. Use pointer i for string s and j for string t
2. Traverse t with j
3. When s[i] == t[j], move i forward (found a match)
4. Always move j forward
5. If i reaches end of s, all characters found in order

C# Solution

public class Solution 
{
    public bool IsSubsequence(string s, string t) 
    {
        int i = 0, j = 0;
        
        while (i < s.Length && j < t.Length)
        {
            // If characters match, move pointer in s
            if (s[i] == t[j])
            {
                i++;
            }
            // Always move pointer in t
            j++;
        }
        
        // If we've matched all characters in s, it's a subsequence
        return i == s.Length;
    }
}

Python 3 Solution

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = j = 0
        
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        
        return i == len(s)

Complexity Analysis

• Time Complexity: O(n) where n is the length of t
• Space Complexity: O(1)

Key Insight

We only advance i when we find a match. If i reaches the end of s, we’ve found all characters in order, making s a subsequence of t.

Problem 3: Next Permutation

Problem Statement

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example

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

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

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

Understanding the Problem

We need to find the next lexicographically greater permutation. The algorithm:

1. Find the largest index i such that nums[i] < nums[i+1]
2. Find the largest index j > i such that nums[j] > nums[i]
3. Swap nums[i] and nums[j]
4. Reverse the suffix starting at i+1

Solution Strategy

Algorithm Steps:

1. Traverse from right to find first decreasing element (pivot)
2. If no pivot found, reverse entire array (already last permutation)
3. Find smallest element greater than pivot in suffix
4. Swap pivot with that element
5. Reverse the suffix to get lexicographically smallest suffix

C# Solution

public class Solution 
{
    public void NextPermutation(int[] nums) 
    {
        int n = nums.Length;
        if (n < 2)
            return;
        
        // Step 1: Find the largest index i such that nums[i] < nums[i+1]
        int index = n - 1;
        while (index > 0)
        {
            if (nums[index - 1] < nums[index])
                break;
            index--;
        }
        
        // If no such index exists, array is in descending order
        // Reverse to get first permutation (ascending order)
        if (index == 0)
        {
            ReverseSort(nums, 0, n - 1);
            return;
        }
        
        // Step 2: Find the largest index j > index-1 such that nums[j] > nums[index-1]
        int val = nums[index - 1];
        int j = n - 1;
        while (j >= index)
        {
            if (nums[j] > val)
                break;
            j--;
        }
        
        // Step 3: Swap nums[index-1] and nums[j]
        Swap(nums, j, index - 1);
        
        // Step 4: Reverse the suffix starting at index
        ReverseSort(nums, index, n - 1);
    }
    
    private void Swap(int[] num, int i, int j)
    {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    
    private void ReverseSort(int[] num, int start, int end)
    {
        if (start > end)
            return;
        
        for (int i = start; i <= (end + start) / 2; i++)
        {
            Swap(num, i, start + end - i);
        }
    }
}

Python 3 Solution

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        def swap(nums: List[int], i: int, j: int) -> None:
            temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp
        
        def reverseSort(nums: List[int], start: int, end: int) -> None:
            if start > end:
                return
            for i in range(start, (start + end) // 2 + 1):
                swap(nums, i, start + end - i)
        
        n = len(nums)
        if n < 2:
            return
        
        # Step 1: Find pivot
        index = n - 1
        while index > 0:
            if nums[index - 1] < nums[index]:
                break
            index -= 1
        
        # If no pivot, reverse entire array
        if index == 0:
            reverseSort(nums, 0, n - 1)
            return
        
        # Step 2: Find element to swap with pivot
        val = nums[index - 1]
        j = n - 1
        while j >= index:
            if nums[j] > val:
                break
            j -= 1
        
        # Step 3: Swap
        swap(nums, j, index - 1)
        
        # Step 4: Reverse suffix
        reverseSort(nums, index, n - 1)

Complexity Analysis

• Time Complexity: O(n) where n is the length of nums
• Space Complexity: O(1) – only using constant extra space

Key Insight

The algorithm finds the rightmost position where we can make a lexicographically larger permutation by swapping with a larger element from the suffix, then makes the suffix as small as possible.

Problem 4: String to Integer (atoi)

Problem Statement

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range [-2³¹, 2³¹ - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2³¹ should be clamped to -2³¹, and integers greater than 2³¹ - 1 should be clamped to 2³¹ - 1.
6. Return the integer as the final result.

Example

Input: s = "42"
Output: 42

Input: s = "   -42"
Output: -42

Input: s = "4193 with words"
Output: 4193

Understanding the Problem

We need to parse a string and convert it to an integer, handling:

• Leading whitespace
• Optional sign (+ or -)
• Digits only
• Integer overflow/underflow

Solution Strategy

Step-by-Step Parsing:

1. Skip leading whitespace
2. Read optional sign
3. Read digits and build number
4. Check for overflow before multiplying by 10
5. Return clamped value if overflow occurs

C# Solution

public class Solution 
{
    public int MyAtoi(string s) 
    {
        int sign = 1;
        int result = 0;
        int index = 0;
        int n = s.Length;
        
        // Step 1: Discard all spaces from the beginning
        while (index < n && s[index] == ' ')
        {
            index++;
        }
        
        // Step 2: Read optional sign
        if (index < n && s[index] == '+')
        {
            sign = 1;
            index++;
        }
        else if (index < n && s[index] == '-')
        {
            sign = -1;
            index++;
        }
        
        // Step 3: Read digits and build number
        while (index < n && Char.IsDigit(s[index]))
        {
            int digit = s[index] - '0';
            
            // Step 4: Check overflow before multiplying
            if (result > Int32.MaxValue / 10 || 
                (result == Int32.MaxValue / 10 && digit > Int32.MaxValue % 10))
            {
                // Clamp to integer limits
                return sign == 1 ? Int32.MaxValue : Int32.MinValue;
            }
            
            // Append current digit to the result
            result = 10 * result + digit;
            index++;
        }
        
        // Step 5: Return result with sign
        return sign * result;
    }
}

Python 3 Solution

class Solution:
    def myAtoi(self, s: str) -> int:
        sign = 1
        result = 0
        index = 0
        n = len(s)
        INT_MAX = pow(2, 31) - 1
        INT_MIN = -pow(2, 31)
        
        # Step 1: Discard all spaces from the beginning
        while index < n and s[index] == ' ':
            index += 1
        
        # Step 2: Read optional sign
        if index < n and s[index] == '+':
            sign = 1
            index += 1
        elif index < n and s[index] == '-':
            sign = -1
            index += 1
        
        # Step 3: Read digits and build number
        while index < n and s[index].isdigit():
            digit = int(s[index])
            
            # Step 4: Check overflow before multiplying
            if (result > INT_MAX // 10 or 
                (result == INT_MAX // 10 and digit > INT_MAX % 10)):
                # Clamp to integer limits
                return INT_MAX if sign == 1 else INT_MIN
            
            # Append current digit to the result
            result = 10 * result + digit
            index += 1
        
        # Step 5: Return result with sign
        return sign * result

Complexity Analysis

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

Key Insight

We check for overflow before multiplying by 10 and adding the digit. This prevents actual integer overflow and allows us to clamp to the limits correctly.

Problem 5: Zigzag Conversion

Problem Statement

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows.

Example

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Understanding the Problem

We need to write the string in a zigzag pattern and then read it row by row. The pattern has a cycle length of 2 * numRows - 2.

Solution Strategy

Pattern-Based Approach:

1. For each row, identify the pattern of character positions
2. The cycle length is 2 * numRows - 2
3. For row i:
   • Characters appear at positions: j + i where j is a multiple of cycle length
   • For middle rows, there’s also a character at j + cycleLen - i

C# Solution

public class Solution 
{
    public string Convert(string s, int numRows) 
    {
        // Edge case: single row
        if (numRows == 1) 
            return s;
        
        StringBuilder ret = new StringBuilder();
        int n = s.Length;
        int cycleLen = 2 * numRows - 2;
        
        for (int i = 0; i < numRows; i++)
        {
            for (int j = 0; j + i < n; j += cycleLen)
            {
                // Add character from main column
                ret.Append(s[j + i]);
                
                // For middle rows, add character from diagonal
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                {
                    ret.Append(s[j + cycleLen - i]);
                }
            }
        }
        
        return ret.ToString();
    }
}

Python 3 Solution

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # Edge case: single row
        if numRows == 1:
            return s
        
        result = []
        n = len(s)
        cycleLen = 2 * numRows - 2
        
        for i in range(numRows):
            j = 0
            while j + i < n:
                # Add character from main column
                result.append(s[j + i])
                
                # For middle rows, add character from diagonal
                if i != 0 and i != numRows - 1 and j + cycleLen - i < n:
                    result.append(s[j + cycleLen - i])
                
                j += cycleLen
        
        return ''.join(result)

Complexity Analysis

• Time Complexity: O(n) where n is the length of the string
• Space Complexity: O(n) for the result string

Key Insight

The zigzag pattern has a repeating cycle. For each row, we can calculate exactly which characters belong to that row based on the cycle length and row index.

Key Takeaways

Array Manipulation Techniques:

1. Two Pointers

• Use when you need to process elements from different positions
• Often reduces time complexity
• Examples: Move Zeroes, Is Subsequence

2. In-Place Operations

• Modify arrays without extra space
• Use swapping or overwriting
• Examples: Move Zeroes, Next Permutation

3. Pattern Recognition

• Identify mathematical patterns or cycles
• Use formulas to calculate positions
• Examples: Zigzag Conversion

String Manipulation Techniques:

1. Character-by-Character Parsing

• Process strings one character at a time
• Handle edge cases carefully
• Examples: String to Integer (atoi)

2. Index Calculation

• Use mathematical formulas for positions
• Consider cycles and patterns
• Examples: Zigzag Conversion

3. State Tracking

• Track sign, whitespace, digits
• Handle transitions between states
• Examples: String to Integer (atoi)

Common Patterns:

1. Two Pointers

• One pointer for each array/string
• Move pointers based on conditions
• Often O(n) time complexity

2. In-Place Swapping

• Swap elements to rearrange
• Use temporary variable or XOR
• Maintain relative order when needed

3. Overflow Handling

• Check before operations
• Use limits to clamp values
• Handle both positive and negative

Best Practices:

1. Handle Edge Cases

• Empty arrays/strings
• Single element
• All zeros or all same values
• Integer overflow

2. Optimize Space

• Use in-place operations when possible
• Reuse existing arrays/strings
• Avoid unnecessary copies

3. Clear Variable Names

• Use descriptive names for pointers
• Name variables by their purpose
• Make code self-documenting

4. Test Boundary Conditions

• Minimum and maximum values
• Empty inputs
• Single character/element
• Edge cases in algorithms

Conclusion

Array and string manipulation problems are fundamental and appear frequently in coding interviews. Mastering these techniques—two pointers, in-place operations, pattern recognition, and careful parsing—will help you solve a wide variety of problems efficiently.

Key techniques to remember:

• Two Pointers: Process elements from different positions simultaneously
• In-Place Operations: Modify data structures without extra space
• Pattern Recognition: Identify cycles and mathematical relationships
• Careful Parsing: Handle edge cases and state transitions

Practice these problems to build intuition for when to apply each technique. The more you practice, the better you’ll become at recognizing patterns and implementing efficient solutions.

Remember: Always consider edge cases, optimize for both time and space complexity, and write clean, readable code that handles all possible inputs correctly.

Happy coding!