C++ Programming Problems

This page contains carefully selected C++ problems covering Arrays, Pointers, and Binary Search. Each problem includes theory, examples, and complete solutions.

Table of Contents

  1. Arrays: Theory & Concepts
  2. Array Problems
  3. Pointers: Theory & Concepts
  4. Pointer Problems
  5. Binary Search: Theory & Concepts
  6. Binary Search Problems

1. Arrays: Theory & Concepts

What is an Array?

An array is a collection of elements of the same type stored in contiguous memory locations. Arrays provide O(1) random access but have fixed size (in C++).

Key Properties

  • Declaration: int arr[10]; or int arr[] = {1, 2, 3};
  • Indexing: Zero-based (first element at index 0)
  • Memory: Contiguous block, size = n × sizeof(type)
  • Access: O(1) via index, O(n) for search
  • Size: Fixed at compile time (static arrays)

Array Operations

// Basic array operations int arr[5] = {10, 20, 30, 40, 50}; // Access: O(1) int val = arr[2]; // 30 arr[3] = 99; // Modify // Traversal: O(n) for (int i = 0; i < 5; i++) cout << arr[i] << " "; // Search: O(n) bool found = false; for (int i = 0; i < 5; i++) if (arr[i] == 30) { found = true; break; }

Common Array Patterns

  • Two Pointers: Start from both ends, move towards center
  • Sliding Window: Maintain a window of elements
  • Prefix Sum: Precompute cumulative sums for range queries
  • In-place Operations: Modify array without extra space

2. Array Problems

Problem 1: Find Maximum Element Easy

Problem: Given an array of integers, find the maximum element.

Example:

Input: arr = [3, 7, 2, 9, 1]
Output: 9

Solution:

#include <iostream> #include <climits> using namespace std; int findMax(int arr[], int n) { int maxVal = INT_MIN; for (int i = 0; i < n; i++) { if (arr[i] > maxVal) maxVal = arr[i]; } return maxVal; } // Alternative: using pointer int findMaxPtr(int* arr, int n) { int maxVal = *arr; // first element for (int i = 1; i < n; i++) { if (*(arr + i) > maxVal) maxVal = *(arr + i); } return maxVal; } int main() { int arr[] = {3, 7, 2, 9, 1}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Max: " << findMax(arr, n) << endl; return 0; }

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

Problem 2: Reverse Array Easy

Problem: Reverse an array in-place (without using extra array).

Example:

Input: arr = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Solution: Two Pointers Technique

#include <iostream> using namespace std; void reverseArray(int arr[], int n) { int left = 0, right = n - 1; while (left < right) { // Swap elements int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } // Using pointers void reverseArrayPtr(int* arr, int n) { int* left = arr; int* right = arr + n - 1; while (left < right) { swap(*left, *right); left++; right--; } } int main() { int arr[] = {1, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); reverseArray(arr, n); for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; }

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

Problem 3: Two Sum Medium

Problem: Given an array of integers and a target sum, find two indices such that their values add up to the target.

Example:

Input: arr = [2, 7, 11, 15], target = 9
Output: [0, 1] (because arr[0] + arr[1] = 2 + 7 = 9)

Solution: Hash Map Approach (O(n))

#include <iostream> #include <unordered_map> #include <vector> using namespace std; vector<int> twoSum(int arr[], int n, int target) { unordered_map<int, int> map; for (int i = 0; i < n; i++) { int complement = target - arr[i]; if (map.find(complement) != map.end()) { return {map[complement], i}; } map[arr[i]] = i; } return {}; // not found } // Alternative: Two pointers (if array is sorted) vector<int> twoSumSorted(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 {left, right}; else if (sum < target) left++; else right--; } return {}; } int main() { int arr[] = {2, 7, 11, 15}; int n = sizeof(arr) / sizeof(arr[0]); vector<int> result = twoSum(arr, n, 9); cout << "Indices: [" << result[0] << ", " << result[1] << "]" << endl; return 0; }

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

Problem 4: Maximum Subarray Sum (Kadane's Algorithm) Medium

Problem: Find the maximum sum of a contiguous subarray.

Example:

Input: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 (subarray [4, -1, 2, 1])

Solution: Kadane's Algorithm

#include <iostream> #include <climits> using namespace std; int maxSubarraySum(int arr[], int n) { int maxSoFar = INT_MIN; int maxEndingHere = 0; for (int i = 0; i < n; i++) { maxEndingHere += arr[i]; if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere; if (maxEndingHere < 0) maxEndingHere = 0; // reset if negative } return maxSoFar; } // With indices tracking int maxSubarraySumWithIndices(int arr[], int n, int& start, int& end) { int maxSoFar = INT_MIN; int maxEndingHere = 0; int tempStart = 0; for (int i = 0; i < n; i++) { maxEndingHere += arr[i]; if (maxSoFar < maxEndingHere) { maxSoFar = maxEndingHere; start = tempStart; end = i; } if (maxEndingHere < 0) { maxEndingHere = 0; tempStart = i + 1; } } return maxSoFar; } int main() { int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Max sum: " << maxSubarraySum(arr, n) << endl; return 0; }

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

Problem 5: Merge Sorted Arrays Hard

Problem: Merge two sorted arrays into one sorted array in-place (first array has enough space).

Example:

Input: arr1 = [1, 3, 5, 0, 0, 0], m = 3
       arr2 = [2, 4, 6], n = 3
Output: arr1 = [1, 2, 3, 4, 5, 6]

Solution: Two Pointers from End

#include <iostream> using namespace std; void mergeSortedArrays(int arr1[], int m, int arr2[], int n) { // Start from the end of both arrays int i = m - 1; // last element of arr1 int j = n - 1; // last element of arr2 int k = m + n - 1; // last position in merged array while (i >= 0 && j >= 0) { if (arr1[i] > arr2[j]) { arr1[k] = arr1[i]; i--; } else { arr1[k] = arr2[j]; j--; } k--; } // Copy remaining elements from arr2 while (j >= 0) { arr1[k] = arr2[j]; j--; k--; } } int main() { int arr1[6] = {1, 3, 5, 0, 0, 0}; int arr2[] = {2, 4, 6}; mergeSortedArrays(arr1, 3, arr2, 3); for (int i = 0; i < 6; i++) cout << arr1[i] << " "; return 0; }

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

3. Pointers: Theory & Concepts

What is a Pointer?

A pointer is a variable that stores the memory address of another variable. Pointers enable dynamic memory allocation, efficient array access, and function parameter passing by reference.

Key Concepts

  • Declaration: int* ptr; or int *ptr;
  • Address-of: &variable gets the address
  • Dereference: *ptr gets the value at address
  • Null pointer: nullptr or NULL (points to nothing)
  • Pointer arithmetic: ptr + 1 moves by sizeof(type) bytes

Pointer Operations

// Basic pointer operations int x = 10; int* ptr = &x; // ptr stores address of x cout << x << endl; // 10 cout << *ptr << endl; // 10 (dereference) cout << ptr << endl; // address (e.g., 0x7fff5fbff6ac) *ptr = 20; // modify x through pointer cout << x << endl; // 20 // Pointer arithmetic int arr[] = {1, 2, 3, 4, 5}; int* p = arr; // p points to arr[0] cout << *p << endl; // 1 cout << *(p + 2) << endl; // 3 (arr[2])

Common Pointer Patterns

  • Pass by Reference: Modify variables in functions
  • Dynamic Allocation: new and delete
  • Array Traversal: Use pointers instead of indices
  • Function Pointers: Pass functions as parameters

4. Pointer Problems

Problem 6: Swap Using Pointers Easy

Problem: Write a function to swap two integers using pointers.

Example:

Input: a = 5, b = 10
Output: a = 10, b = 5

Solution:

#include <iostream> using namespace std; void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // Using references (C++ style) void swapRef(int& a, int& b) { int temp = a; a = b; b = temp; } int main() { int x = 5, y = 10; cout << "Before: x=" << x << ", y=" << y << endl; swap(&x, &y); // pass addresses cout << "After: x=" << x << ", y=" << y << endl; return 0; }

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

Problem 7: Find Array Sum Using Pointers Easy

Problem: Calculate the sum of array elements using pointer arithmetic.

Example:

Input: arr = [1, 2, 3, 4, 5]
Output: 15

Solution:

#include <iostream> using namespace std; int arraySum(int* arr, int n) { int sum = 0; int* end = arr + n; // pointer to one past last element for (int* p = arr; p < end; p++) { sum += *p; } return sum; } // Alternative: using pointer arithmetic int arraySumAlt(int* arr, int n) { int sum = 0; for (int i = 0; i < n; i++) { sum += *(arr + i); // same as arr[i] } return sum; } int main() { int arr[] = {1, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Sum: " << arraySum(arr, n) << endl; return 0; }

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

Problem 8: Reverse Array Using Pointers Medium

Problem: Reverse an array using only pointers (no index notation).

Example:

Input: arr = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Solution:

#include <iostream> using namespace std; void reverseArrayPtr(int* arr, int n) { int* left = arr; // pointer to first element int* right = arr + n - 1; // pointer to last element while (left < right) { // Swap using pointers int temp = *left; *left = *right; *right = temp; left++; right--; } } // Using swap function void reverseArrayPtrSwap(int* arr, int n) { int* start = arr; int* end = arr + n - 1; while (start < end) { swap(*start, *end); start++; end--; } } int main() { int arr[] = {1, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); reverseArrayPtr(arr, n); for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; }

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

Problem 9: Find Maximum Using Pointers Medium

Problem: Find the maximum element in an array and return its address using pointers.

Example:

Input: arr = [3, 7, 2, 9, 1]
Output: Address of element 9

Solution:

#include <iostream> using namespace std; int* findMaxPtr(int* arr, int n) { if (n == 0) return nullptr; int* maxPtr = arr; // assume first is max int* end = arr + n; for (int* p = arr + 1; p < end; p++) { if (*p > *maxPtr) { maxPtr = p; } } return maxPtr; } int main() { int arr[] = {3, 7, 2, 9, 1}; int n = sizeof(arr) / sizeof(arr[0]); int* maxPtr = findMaxPtr(arr, n); if (maxPtr != nullptr) { cout << "Max value: " << *maxPtr << endl; cout << "Address: " << maxPtr << endl; cout << "Index: " << (maxPtr - arr) << endl; } return 0; }

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

Problem 10: Dynamic Array Operations Hard

Problem: Implement a dynamic array (vector-like) with push, pop, and resize operations using pointers.

Requirements:

  • Allocate memory dynamically
  • Resize when capacity is full
  • Implement push_back and pop_back

Solution:

#include <iostream> using namespace std; class DynamicArray { private: int* data; int size; int capacity; void resize() { capacity *= 2; int* newData = new int[capacity]; for (int i = 0; i < size; i++) { newData[i] = data[i]; } delete[] data; data = newData; } public: DynamicArray(int cap = 4) : size(0), capacity(cap) { data = new int[capacity]; } ~DynamicArray() { delete[] data; } void push_back(int value) { if (size >= capacity) { resize(); } data[size++] = value; } void pop_back() { if (size > 0) { size--; } } int& operator[](int index) { return data[index]; } int getSize() const { return size; } int getCapacity() const { return capacity; } void print() { for (int i = 0; i < size; i++) { cout << data[i] << " "; } cout << endl; } }; int main() { DynamicArray arr; arr.push_back(1); arr.push_back(2); arr.push_back(3); arr.print(); cout << "Size: " << arr.getSize() << ", Capacity: " << arr.getCapacity() << endl; return 0; }

Time Complexity: Push O(1) amortized, Pop O(1) | Space Complexity: O(n)

5. Binary Search: Theory & Concepts

What is Binary Search?

Binary Search is an efficient algorithm for finding an element in a sorted array. It repeatedly divides the search space in half, achieving O(log n) time complexity.

Key Properties

  • Prerequisite: Array must be sorted
  • Time Complexity: O(log n)
  • Space Complexity: O(1) iterative, O(log n) recursive
  • Approach: Divide and conquer
  • Comparison: Compare target with middle element

Binary Search Algorithm

// Classic binary search int binarySearch(int arr[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; // avoid overflow if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; // search right half else right = mid - 1; // search left half } return -1; // not found }

Binary Search Variations

  • Find First Occurrence: Continue searching left when found
  • Find Last Occurrence: Continue searching right when found
  • Find Insertion Position: Return left pointer
  • Search in Rotated Array: Handle rotation point

6. Binary Search Problems

Problem 11: Binary Search Easy

Problem: Implement binary search to find a target in a sorted array.

Example:

Input: arr = [1, 3, 5, 7, 9, 11], target = 7
Output: 3 (index of 7)

Solution:

#include <iostream> using namespace std; int binarySearch(int arr[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } // Recursive version int binarySearchRec(int arr[], int left, int right, int target) { if (left > right) return -1; int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) return binarySearchRec(arr, mid + 1, right, target); else return binarySearchRec(arr, left, mid - 1, target); } int main() { int arr[] = {1, 3, 5, 7, 9, 11}; int n = sizeof(arr) / sizeof(arr[0]); int target = 7; int index = binarySearch(arr, n, target); cout << "Found at index: " << index << endl; return 0; }

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

Problem 12: Find First Occurrence Easy

Problem: Find the first occurrence of a target in a sorted array (may contain duplicates).

Example:

Input: arr = [1, 2, 2, 2, 3, 4], target = 2
Output: 1 (first index where 2 appears)

Solution:

#include <iostream> using namespace std; int findFirst(int arr[], int n, int target) { int left = 0, right = n - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; right = mid - 1; // continue searching left } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } int main() { int arr[] = {1, 2, 2, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); cout << "First occurrence: " << findFirst(arr, n, 2) << endl; return 0; }

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

Problem 13: Search Insert Position Medium

Problem: Find the index where a target should be inserted to keep the array sorted.

Example:

Input: arr = [1, 3, 5, 6], target = 5
Output: 2 (already exists)

Input: arr = [1, 3, 5, 6], target = 2
Output: 1 (should be inserted at index 1)

Solution:

#include <iostream> using namespace std; int searchInsert(int arr[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return left; // insertion position } int main() { int arr[] = {1, 3, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Insert position for 2: " << searchInsert(arr, n, 2) << endl; cout << "Insert position for 5: " << searchInsert(arr, n, 5) << endl; return 0; }

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

Problem 14: Find Peak Element Medium

Problem: A peak element is greater than its neighbors. Find any peak element (array may not be sorted).

Example:

Input: arr = [1, 2, 3, 1]
Output: 2 (index of element 3, which is a peak)

Solution: Binary Search on Conditions

#include <iostream> using namespace std; int findPeak(int arr[], int n) { int left = 0, right = n - 1; while (left < right) { int mid = left + (right - left) / 2; // If mid is less than next, peak is on right if (arr[mid] < arr[mid + 1]) left = mid + 1; else right = mid; // peak is on left or mid } return left; } int main() { int arr[] = {1, 2, 3, 1}; int n = sizeof(arr) / sizeof(arr[0]); int peakIndex = findPeak(arr, n); cout << "Peak at index: " << peakIndex << ", value: " << arr[peakIndex] << endl; return 0; }

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

Problem 15: Search in Rotated Sorted Array Hard

Problem: Search for a target in a rotated sorted array (e.g., [4,5,6,7,0,1,2] rotated at index 4).

Example:

Input: arr = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Solution:

#include <iostream> using namespace std; int searchRotated(int arr[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; // Left half is sorted if (arr[left] <= arr[mid]) { if (target >= arr[left] && target < arr[mid]) right = mid - 1; else left = mid + 1; } // Right half is sorted else { if (target > arr[mid] && target <= arr[right]) left = mid + 1; else right = mid - 1; } } return -1; } int main() { int arr[] = {4, 5, 6, 7, 0, 1, 2}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Index of 0: " << searchRotated(arr, n, 0) << endl; return 0; }

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