#2 - Arrays and Strings - Data Structures and Algorithms using C++ | Akash Vishwakarma

1. Introduction

Arrays and strings form the backbone of programming and data structures. Before trees, graphs, machine learning models, or distributed systems, everything starts with how data is stored and accessed in memory.

In coding interviews, arrays and strings dominate because they test multiple skills at once: logical thinking, time–space complexity analysis, edge-case handling, and clean coding practices.

This article is written to do three things:

• Build strong conceptual foundations
• Explain common techniques used in real problem solving
• Prepare you for interviews with clarity, not memorization

Every technique discussed here appears repeatedly in competitive programming, LeetCode, Codeforces, and product-company interviews.

2. Understanding Arrays

An array is a collection of elements stored in contiguous memory locations. This contiguity is the key reason arrays provide fast access.

2.1 Memory Representation

When you declare an array like int arr[5], the compiler allocates a continuous block of memory large enough to store 5 integers.

Because the memory is contiguous, the address of any element can be calculated using the formula:

address(arr[i]) = base_address + i × size_of_element
  

This is why accessing arr[i] takes constant time — O(1).

2.2 Advantages of Arrays

• Fast random access (O(1))
• Cache-friendly due to contiguous memory
• Simple and predictable structure

2.3 Limitations of Arrays

• Fixed size (in static arrays)
• Insertion and deletion are costly (O(n))
• Memory wastage if size is overestimated

3. Basic Operations on Arrays

3.1 Traversal

Traversal means visiting each element exactly once. Almost every array problem starts with traversal.

int arr[] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
    cout << arr[i] << " ";
}
  

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

3.2 Insertion

Inserting an element at a specific index requires shifting elements to the right. This is unavoidable in arrays.

int arr[6] = {1, 2, 3, 4, 5};
int pos = 2, n = 5, value = 10;

for (int i = n; i > pos; i--) {
    arr[i] = arr[i - 1];
}
arr[pos] = value;
  

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

3.3 Deletion

Deletion shifts elements left to fill the gap.

int arr[] = {1, 2, 3, 4, 5};
int pos = 2;

for (int i = pos; i < 4; i++) {
    arr[i] = arr[i + 1];
}
  

4. Multi-Dimensional Arrays

Multi-dimensional arrays store data in more than one dimension. The most common is the 2D array.

int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
  

Use cases include:

• Matrix operations
• Board games (chess, sudoku)
• Dynamic programming tables

5. Core Array Techniques Used in Interviews

5.1 Sliding Window Technique

The sliding window technique optimizes problems involving contiguous subarrays or substrings.

Instead of recalculating values repeatedly, we reuse previous computations.

int maxSum(int arr[], int n, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++)
        windowSum += arr[i];

    int maxSum = windowSum;

    for (int i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}
  

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

5.2 Two-Pointer Technique

Two pointers reduce brute-force nested loops. They are especially effective on sorted arrays.

bool hasPair(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return true;
        else if (sum < target) left++;
        else right--;
    }
    return false;
}
  

6. Strings: Concepts and Internals

A string is a sequence of characters. In C/C++, strings are arrays of characters.

6.1 Palindrome Checking

bool isPalindrome(string s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}
  

6.2 Anagram Detection

Anagrams rely on frequency matching, not sorting.

bool isAnagram(string a, string b) {
    if (a.length() != b.length()) return false;
    int freq[26] = {0};

    for (char c : a) freq[c - 'a']++;
    for (char c : b) {
        if (--freq[c - 'a'] < 0) return false;
    }
    return true;
}
  

7. Subarray Algorithms

Kadane’s Algorithm

Kadane’s Algorithm solves the maximum subarray sum problem in linear time.

int kadane(int arr[], int n) {
    int maxSum = INT_MIN;
    int currentSum = 0;

    for (int i = 0; i < n; i++) {
        currentSum = max(arr[i], currentSum + arr[i]);
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}
  

8. Interview Questions and Thinking Patterns

1. Why are arrays preferred over linked lists for random access?

   Because arrays allow O(1) access using index arithmetic, while linked lists require O(n) traversal.

2. Why does Kadane’s Algorithm work?

   Because a negative prefix can never improve a future sum.

3. How to check string rotation?

   
   bool isRotation(string s1, string s2) {
       return s1.length() == s2.length() &&
              (s1 + s1).find(s2) != string::npos;
   }
         

9. Final Advice

Arrays and strings are not about memorizing solutions. They are about recognizing patterns.

If you master:

• Sliding Window
• Two Pointers
• Hashing
• Prefix sums

You can solve over 70% of DSA interview problems.