Arrays, Pointers and Functions

Understanding pointers is fundamental to mastering C++ programming. Pointers provide direct access to memory addresses, enabling efficient manipulation of data structures, function parameters, and dynamic memory allocation. This guide explores how pointers work with arrays and functions, and why they are essential for writing efficient C++ code.

What are Pointers?

A pointer is a variable that stores the memory address of another variable. Instead of holding a value directly, a pointer holds the location where a value is stored in memory.

Basic Pointer Syntax

int x = 10;        // Regular variable
int* ptr = &x;     // Pointer to x (stores address of x)
// ptr now contains the memory address where x is stored
// *ptr dereferences the pointer to access the value (10)

Key Pointer Operations

  • & (address-of operator): Gets the memory address of a variable
  • * (dereference operator): Accesses the value at the address stored in the pointer
  • ptr: The pointer variable itself (contains an address)
  • *ptr: The value at the address stored in ptr

Why Are Pointers Important?

  • Memory Efficiency: Pass large data structures by reference instead of copying entire objects
  • Dynamic Memory Allocation: Allocate and deallocate memory at runtime using new and delete
  • Array Manipulation: Efficiently traverse and manipulate arrays
  • Function Parameters: Modify variables passed to functions (pass by reference)
  • Data Structures: Essential for implementing linked lists, trees, and graphs
  • Performance: Avoid expensive copy operations, especially with large objects

Pointers and Arrays

In C++, arrays and pointers are closely related. The name of an array is essentially a pointer to its first element.

Array-Pointer Relationship

int arr[5] = {10, 20, 30, 40, 50};

// These are equivalent:
int* ptr1 = arr;        // Array name is a pointer to first element
int* ptr2 = &arr[0];    // Explicitly get address of first element

// Array indexing using pointers:
arr[2]    // Access element at index 2
*(arr + 2) // Same as arr[2] using pointer arithmetic
ptr1[2]   // Same as arr[2]
*(ptr1 + 2) // Same as arr[2]

Pointer Arithmetic

When you add an integer to a pointer, it moves forward by that many elements (not bytes). The compiler automatically accounts for the size of the data type.

int arr[5] = {10, 20, 30, 40, 50};
int* ptr = arr;

ptr + 0  // Points to arr[0] (value: 10)
ptr + 1  // Points to arr[1] (value: 20)
ptr + 2  // Points to arr[2] (value: 30)
*(ptr + 2) // Dereferences to get value 30

Visual Representation

Array and Pointer Relationship

Memory Addresses 0x1000 0x1004 0x1008 0x100C 0x1010 Array: int arr[5] = {10, 20, 30, 40, 50} 10 arr[0] 20 arr[1] 30 arr[2] 40 arr[3] 50 arr[4] Pointer: int* ptr = arr 0x1000 ptr Points to arr[0] Pointer Arithmetic ptr + 0 → arr[0] = 10 ptr + 1 → arr[1] = 20 ptr + 2 → arr[2] = 30 *(ptr + 2) = 30 ptr[2] = 30

Pointers and Functions

Pointers enable functions to modify variables passed as arguments and efficiently handle arrays and large data structures.

Pass by Value vs Pass by Reference

// Pass by Value (creates a copy)
void incrementByValue(int x) {
    x++;  // Only modifies the copy
}

// Pass by Pointer (modifies original)
void incrementByPointer(int* x) {
    (*x)++;  // Modifies the original variable
}

// Pass by Reference (C++ style, cleaner)
void incrementByReference(int& x) {
    x++;  // Modifies the original variable
}

int num = 5;
incrementByValue(num);      // num is still 5
incrementByPointer(&num);   // num becomes 6
incrementByReference(num);  // num becomes 7

Passing Arrays to Functions

When you pass an array to a function, you're actually passing a pointer to the first element. Arrays are always passed by reference (pointer).

// These function signatures are equivalent:
void printArray(int arr[], int size);
void printArray(int* arr, int size);

void printArray(int* arr, int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";  // Can use array notation
        // or
        cout << *(arr + i) << " ";  // Can use pointer notation
    }
}

int numbers[5] = {1, 2, 3, 4, 5};
printArray(numbers, 5);  // Pass array name (pointer)

Returning Pointers from Functions

// Return pointer to dynamically allocated memory
int* createArray(int size) {
    int* arr = new int[size];
    for (int i = 0; i < size; i++) {
        arr[i] = i * 2;
    }
    return arr;  // Return pointer to first element
}

int* myArray = createArray(10);
// Use myArray...
delete[] myArray;  // Don't forget to free memory!

Function Pointers

Pointers can also point to functions, enabling dynamic function calls and callbacks.

// Function pointer syntax
int add(int a, int b) { return a + b; }
int multiply(int a, int b) { return a * b; }

int (*operation)(int, int);  // Function pointer declaration

operation = add;        // Point to add function
int result1 = operation(5, 3);  // Calls add(5, 3) → 8

operation = multiply;   // Point to multiply function
int result2 = operation(5, 3);  // Calls multiply(5, 3) → 15

Common Pointer Pitfalls

  • Dangling Pointers: Pointers that reference memory that has been freed
  • Memory Leaks: Forgetting to free dynamically allocated memory
  • Null Pointer Dereference: Accessing memory through a null pointer
  • Uninitialized Pointers: Using pointers before assigning them a valid address
  • Array Bounds: Accessing array elements outside valid range

Best Practices

  • Always initialize pointers (use nullptr if not immediately assigned)
  • Check for null pointers before dereferencing
  • Use smart pointers (unique_ptr, shared_ptr) in modern C++
  • Match every new with a delete, and new[] with delete[]
  • Prefer references over pointers when you don't need nullability or reassignment
  • Use const pointers when you don't need to modify the pointed-to value

Algorithm Examples

Example 1: Swapping Two Variables Using Pointers

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int x = 10, y = 20;
    cout << "Before: x = " << x << ", y = " << y << endl;
    swap(&x, &y);  // Pass addresses
    cout << "After: x = " << x << ", y = " << y << endl;
    return 0;
}
// Output:
// Before: x = 10, y = 20
// After: x = 20, y = 10

Example 2: Finding Maximum Element in Array

int findMax(int* arr, int size) {
    if (size == 0) return -1;
    
    int max = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

int main() {
    int numbers[] = {3, 7, 2, 9, 1, 5};
    int max = findMax(numbers, 6);
    cout << "Maximum: " << max << endl;  // Output: 9
    return 0;
}

Example 3: Reversing an Array Using Pointers

void reverseArray(int* arr, int size) {
    int* start = arr;
    int* end = arr + size - 1;
    
    while (start < end) {
        // Swap elements at start and end
        int temp = *start;
        *start = *end;
        *end = temp;
        
        start++;
        end--;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    reverseArray(arr, 5);
    // arr is now {5, 4, 3, 2, 1}
    return 0;
}

Example 4: Dynamic Memory Allocation

int* createDynamicArray(int size) {
    int* arr = new int[size];
    
    // Initialize array
    for (int i = 0; i < size; i++) {
        arr[i] = i * i;
    }
    
    return arr;
}

int main() {
    int size = 5;
    int* dynamicArray = createDynamicArray(size);
    
    // Use the array
    for (int i = 0; i < size; i++) {
        cout << dynamicArray[i] << " ";
    }
    // Output: 0 1 4 9 16
    
    // Free the memory
    delete[] dynamicArray;
    return 0;
}

LeetCode Problems

Problem 1: Two Sum (Easy)

Description: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution:

Approach: Use a hash map to store each number and its index. For each number, check if the complement (target - current number) exists in the map.

#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        
        if (map.find(complement) != map.end()) {
            return {map[complement], i};
        }
        
        map[nums[i]] = i;
    }
    
    return {};  // No solution found
}

Time Complexity: O(n) - Single pass through the array

Space Complexity: O(n) - Hash map storage

Problem 2: Remove Duplicates from Sorted Array (Easy)

Description: 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. Return k after placing the final result in the first k slots of nums.

Example:

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.

Solution:

Approach: Use two pointers - one to track the position of unique elements and another to iterate through the array.

#include <vector>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int writeIndex = 1;  // Pointer for writing unique elements
    
    for (int readIndex = 1; readIndex < nums.size(); readIndex++) {
        if (nums[readIndex] != nums[readIndex - 1]) {
            nums[writeIndex] = nums[readIndex];
            writeIndex++;
        }
    }
    
    return writeIndex;
}

Time Complexity: O(n) - Single pass through the array

Space Complexity: O(1) - In-place modification

Problem 3: Best Time to Buy and Sell Stock (Easy)

Description: You are given an array prices where prices[i] is the price of a given stock on the i-th 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:

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.

Solution:

Approach: Track the minimum price seen so far and calculate the maximum profit at each day.

#include <vector>
#include <algorithm>
using namespace std;

int maxProfit(vector<int>& prices) {
    int minPrice = prices[0];
    int maxProfit = 0;
    
    for (int i = 1; i < prices.size(); i++) {
        // Update minimum price seen so far
        minPrice = min(minPrice, prices[i]);
        
        // Calculate profit if we sell today
        int profit = prices[i] - minPrice;
        maxProfit = max(maxProfit, profit);
    }
    
    return maxProfit;
}

Time Complexity: O(n) - Single pass through the array

Space Complexity: O(1) - Constant space

Problem 4: Contains Duplicate (Easy)

Description: Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example:

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

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

Solution:

Approach: Use a hash set to track seen elements. If we encounter an element that's already in the set, return true.

#include <vector>
#include <unordered_set>
using namespace std;

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    
    for (int num : nums) {
        if (seen.find(num) != seen.end()) {
            return true;
        }
        seen.insert(num);
    }
    
    return false;
}

Time Complexity: O(n) - Single pass through the array

Space Complexity: O(n) - Hash set storage

Problem 5: Maximum Subarray (Easy)

Description: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Solution (Kadane's Algorithm):

Approach: Use dynamic programming. At each position, decide whether to extend the previous subarray or start a new one.

#include <vector>
#include <algorithm>
using namespace std;

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        // Either extend the previous subarray or start new
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

Time Complexity: O(n) - Single pass through the array

Space Complexity: O(1) - Constant space

Step-by-Step Simulation:

For nums = [-2,1,-3,4,-1,2,1,-5,4]:

  • i=0: currentSum = -2, maxSum = -2
  • i=1: currentSum = max(1, -2+1) = 1, maxSum = 1
  • i=2: currentSum = max(-3, 1-3) = -2, maxSum = 1
  • i=3: currentSum = max(4, -2+4) = 4, maxSum = 4
  • i=4: currentSum = max(-1, 4-1) = 3, maxSum = 4
  • i=5: currentSum = max(2, 3+2) = 5, maxSum = 5
  • i=6: currentSum = max(1, 5+1) = 6, maxSum = 6
  • i=7: currentSum = max(-5, 6-5) = 1, maxSum = 6
  • i=8: currentSum = max(4, 1+4) = 5, maxSum = 6

Problem 6: Product of Array Except Self (Medium)

Description: Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operator.

Example:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Solution:

Approach: Use two passes - first pass calculates left products, second pass calculates right products and multiplies them together.

#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, 1);
    
    // First pass: Calculate left products
    int leftProduct = 1;
    for (int i = 0; i < n; i++) {
        result[i] = leftProduct;
        leftProduct *= nums[i];
    }
    
    // Second pass: Multiply by right products
    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
}

Time Complexity: O(n) - Two passes through the array

Space Complexity: O(1) - Excluding the output array

Step-by-Step Simulation:

For nums = [1,2,3,4]:

First Pass (Left Products):

  • i=0: result[0] = 1, leftProduct = 1
  • i=1: result[1] = 1, leftProduct = 2
  • i=2: result[2] = 2, leftProduct = 6
  • i=3: result[3] = 6, leftProduct = 24

After first pass: result = [1, 1, 2, 6]

Second Pass (Right Products):

  • i=3: result[3] = 6*1 = 6, rightProduct = 4
  • i=2: result[2] = 2*4 = 8, rightProduct = 12
  • i=1: result[1] = 1*12 = 12, rightProduct = 24
  • i=0: result[0] = 1*24 = 24, rightProduct = 24

Final result: [24, 12, 8, 6]

Problem 7: 3Sum (Medium)

Description: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Example:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

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

Solution:

Approach: Sort the array first, then use two pointers technique. For each element, use two pointers to find pairs that sum to the negative of that element.

#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    int n = nums.size();
    
    if (n < 3) return result;
    
    sort(nums.begin(), nums.end());
    
    for (int i = 0; i < n - 2; i++) {
        // Skip duplicates for the first element
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1;
        int right = n - 1;
        int target = -nums[i];
        
        while (left < right) {
            int sum = nums[left] + nums[right];
            
            if (sum == target) {
                result.push_back({nums[i], nums[left], nums[right]});
                
                // Skip duplicates
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

Time Complexity: O(n²) - Sorting takes O(n log n), and for each element we do a two-pointer scan

Space Complexity: O(1) - Excluding the output array

Step-by-Step Simulation:

For nums = [-1,0,1,2,-1,-4] (sorted: [-4,-1,-1,0,1,2]):

  • i=0, nums[i]=-4: left=1, right=5, target=4, sum=(-1)+2=1 < 4, left++
  • i=0, nums[i]=-4: left=2, right=5, target=4, sum=(-1)+2=1 < 4, left++
  • i=0, nums[i]=-4: left=3, right=5, target=4, sum=0+2=2 < 4, left++
  • i=0, nums[i]=-4: left=4, right=5, target=4, sum=1+2=3 < 4, left++
  • i=1, nums[i]=-1: left=2, right=5, target=1, sum=(-1)+2=1 == 1, found [-1,-1,2]
  • i=1, nums[i]=-1: left=3, right=4, target=1, sum=0+1=1 == 1, found [-1,0,1]
  • i=2, nums[i]=-1: Skip (duplicate of i=1)
  • Continue...

Problem 8: Container With Most Water (Medium)

Description: You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store.

Example:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water the container can contain is 49.

Solution:

Approach: Use two pointers starting from both ends. The area is determined by the shorter line and the distance between lines. Move the pointer pointing to the shorter line inward, as moving the longer line cannot increase the area.

#include <vector>
#include <algorithm>
using namespace std;

int maxArea(vector<int>& height) {
    int left = 0;
    int right = height.size() - 1;
    int maxWater = 0;
    
    while (left < right) {
        // Calculate current area
        int width = right - left;
        int currentArea = min(height[left], height[right]) * width;
        maxWater = max(maxWater, currentArea);
        
        // Move the pointer with smaller height
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxWater;
}

Time Complexity: O(n) - Single pass with two pointers

Space Complexity: O(1) - Constant space

Step-by-Step Simulation:

For height = [1,8,6,2,5,4,8,3,7]:

  • left=0 (h=1), right=8 (h=7): area = min(1,7)*8 = 8, maxWater = 8, left++
  • left=1 (h=8), right=8 (h=7): area = min(8,7)*7 = 49, maxWater = 49, right--
  • left=1 (h=8), right=7 (h=3): area = min(8,3)*6 = 18, maxWater = 49, right--
  • left=1 (h=8), right=6 (h=8): area = min(8,8)*5 = 40, maxWater = 49, left++
  • Continue until left >= right...

Why this works: The area is limited by the shorter line. If we move the pointer with the longer line, the width decreases and the height can't increase (it's still limited by the shorter line), so the area can only decrease. Therefore, we should always move the pointer with the shorter line.