🚀 Top 10 Maths & Arrays Problems

📌 Table of Contents

Palindrome Number
Reverse Integer
Longest Common Prefix
Valid Boomerang
Replace Elements
Top K Frequent Elements
Spiral Matrix II
Rotate Image
Trapping Rain Water
Median of Two Sorted Arrays

1. Palindrome Number

Explanation: Check if a number reads the same forward and backward. Negative numbers are never palindromes because of the minus sign. Numbers ending in 0 (except 0 itself) cannot be palindromes.

🐢 Brute Force

Convert the number into a string, reverse the string, and compare it to the original. This requires extra memory to store the string.

class Solution {
public:
  bool isPalindrome(int x) {
      string s = to_string(x);
      string rev = s;
      reverse(rev.begin(), rev.end());
      return s == rev;
  }
};

🚀 Optimal Approach

Mathematically reverse only the second half of the number. If the reversed second half matches the first half, it's a palindrome.

Time Complexity: O(log10(x))
Space Complexity: O(1)

class Solution {
public:
  bool isPalindrome(int x) {
      if (x < 0 || (x % 10 == 0 && x != 0)) return false;
      
      int revertedNumber = 0;
      while (x > revertedNumber) {
          revertedNumber = revertedNumber * 10 + x % 10;
          x /= 10;
      }
      
      return x == revertedNumber || x == revertedNumber / 10;
  }
};

2. Reverse Integer

Explanation: Reverse the digits of a 32-bit signed integer. If reversing the integer causes it to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], return 0.

🐢 Brute Force

Convert the integer to a string, handle the negative sign separately, reverse the string, and parse it back to an integer inside a try-catch block to handle the overflow.

class Solution {
public:
  int reverse(int x) {
      try {
          string s = to_string(abs(x));
          std::reverse(s.begin(), s.end());
          int res = stoi(s);
          return x < 0 ? -res : res;
      } catch (...) {
          return 0;
      }
  }
};

🚀 Optimal Approach

Use math to pop the last digit (x % 10) and push it to the result (res * 10 + digit). Check for integer overflow before multiplying the result by 10.

Time Complexity: O(log10(x))
Space Complexity: O(1)

class Solution {
public:
  int reverse(int x) {
      int res = 0;
      while (x != 0) {
          int pop = x % 10;
          x /= 10;
          if (res > INT_MAX/10 || (res == INT_MAX / 10 && pop > 7)) return 0;
          if (res < INT_MIN/10 || (res == INT_MIN / 10 && pop < -8)) return 0;
          res = res * 10 + pop;
      }
      return res;
  }
};

3. Longest Common Prefix

Explanation: Find the longest common starting characters among an array of strings. If there is no common prefix, return an empty string.

🐢 Brute Force

Vertical scanning: iterate over the characters of the first string, and check if that exact character appears at the same index in all other strings.

class Solution {
public:
  string longestCommonPrefix(vector<string>& strs) {
      string res = "";
      for (int i = 0; i < strs[0].size(); i++) {
          char c = strs[0][i];
          for (auto &s : strs) {
              if (i >= s.size() || s[i] != c) return res;
          }
          res += c;
      }
      return res;
  }
};

🚀 Optimal Approach

Sort the array of strings alphabetically. The longest common prefix of the entire array will simply be the common prefix between the first and last strings in the sorted array.

Time Complexity: O(N log N * M) where M is max string length.
Space Complexity: O(1) or O(M) for the result string.

class Solution {
public:
  string longestCommonPrefix(vector<string>& strs) {
      sort(strs.begin(), strs.end());
      string first = strs.front();
      string last = strs.back();
      int i = 0;
      while (i < min(first.size(), last.size()) && first[i] == last[i]) {
          i++;
      }
      return first.substr(0, i);
  }
};

4. Valid Boomerang

Explanation: Given an array of three points, check if they form a boomerang (i.e., they are distinct and do not lie on the same straight line).

🐢 Brute Force

Calculate the slope between point 1 & 2, and point 2 & 3 using division (y2-y1)/(x2-x1). This is problematic because x2-x1 can be 0 (vertical lines), throwing a division by zero error, requiring extra edge-case checks and floating-point precision handling.

class Solution {
public:
  bool isBoomerang(vector<vector<int>>& p) {
      if (p[0] == p[1] || p[1] == p[2] || p[0] == p[2]) return false;
      if (p[1][0] - p[0][0] == 0 && p[2][0] - p[1][0] == 0) return false;
      if (p[1][0] - p[0][0] == 0 || p[2][0] - p[1][0] == 0) return true;
      
      double slope1 = (double)(p[1][1] - p[0][1]) / (p[1][0] - p[0][0]);
      double slope2 = (double)(p[2][1] - p[1][1]) / (p[2][0] - p[1][0]);
      return slope1 != slope2;
  }
};

🚀 Optimal Approach

Use cross-multiplication to compare slopes without division. (y2-y1)/(x2-x1) != (y3-y2)/(x3-x2) becomes (y2-y1)*(x3-x2) != (y3-y2)*(x2-x1). This avoids division by zero entirely.

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

class Solution {
public:
  bool isBoomerang(vector<vector<int>>& p) {
      return (p[1][1] - p[0][1]) * (p[2][0] - p[1][0]) != 
             (p[2][1] - p[1][1]) * (p[1][0] - p[0][0]);
  }
};

5. Replace Elements

Explanation: Replace every element in the array with the greatest element strictly to its right, and replace the last element with -1.

🐢 Brute Force

For every element at index i, iterate through the rest of the array (i+1 to n) to find the maximum element and replace arr[i].

Time Complexity: O(N²)

class Solution {
public:
  vector<int> replaceElements(vector<int>& arr) {
      int n = arr.size();
      for(int i = 0; i < n; i++){
          int mx = -1;
          for(int j = i + 1; j < n; j++){
              mx = max(mx, arr[j]);
          }
          arr[i] = mx;
      }
      return arr;
  }
};

🚀 Optimal Approach

Traverse the array from right to left. Keep track of the max_so_far (initially -1). For each step, store the current element, update the current position with max_so_far, and then update max_so_far with the stored element.

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

class Solution {
public:
  vector<int> replaceElements(vector<int>& arr) {
      int mx = -1;
      for (int i = arr.size() - 1; i >= 0; i--) {
          int temp = arr[i];
          arr[i] = mx;
          mx = max(mx, temp);
      }
      return arr;
  }
};

6. Top K Frequent Elements

Explanation: Given an integer array, return the k most frequent elements.

🐢 Brute Force

Count the frequency of each element using a hash map, transfer the key-value pairs to a list, sort the list in descending order by frequency, and pick the first k elements.

Time Complexity: O(N log N)

class Solution {
public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
      unordered_map<int,int> mp;
      for(int n: nums) mp[n]++;
      vector<pair<int,int>> v(mp.begin(), mp.end());
      sort(v.begin(), v.end(), [](auto &a, auto &b){
          return a.second > b.second;
      });
      vector<int> res;
      for(int i = 0; i < k; i++) res.push_back(v[i].first);
      return res;
  }
};

🚀 Optimal Approach

Use Bucket Sort. Since the frequency of any element cannot exceed the length of the array (N), create an array of lists (buckets) where the index represents the frequency. Iterate backwards through the buckets to get the top k elements.

Time Complexity: O(N)
Space Complexity: O(N)

class Solution {
public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
      unordered_map<int, int> count;
      for (int n : nums) count[n]++;
      
      vector<vector<int>> bucket(nums.size() + 1);
      for (auto& [num, freq] : count) {
          bucket[freq].push_back(num);
      }
      
      vector<int> res;
      for (int i = bucket.size() - 1; i >= 0 && res.size() < k; i--) {
          for (int num : bucket[i]) {
              res.push_back(num);
              if (res.size() == k) return res;
          }
      }
      return res;
  }
};

7. Spiral Matrix II

Explanation: Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

🐢 Brute Force (Simulation with Direction Array)

Create a visited matrix or check boundaries, and simulate movement using a direction array (Right, Down, Left, Up). Change direction whenever you hit a wall or a previously filled cell.

class Solution {
public:
  vector<vector<int>> generateMatrix(int n) {
      vector<vector<int>> res(n, vector<int>(n, 0));
      int dx[4] = {0, 1, 0, -1};
      int dy[4] = {1, 0, -1, 0};
      int x = 0, y = 0, dir = 0;
      
      for (int i = 1; i <= n * n; i++) {
          res[x][y] = i;
          int nx = x + dx[dir], ny = y + dy[dir];
          if (nx < 0 || nx >= n || ny < 0 || ny >= n || res[nx][ny] != 0) {
              dir = (dir + 1) % 4;
              nx = x + dx[dir];
              ny = y + dy[dir];
          }
          x = nx; y = ny;
      }
      return res;
  }
};

🚀 Optimal Approach (Boundary Traversal)

Define four boundaries: top, bottom, left, and right. Shrink these boundaries iteratively as you fill the outermost layer of the spiral, loop by loop. This avoids the overhead of checking visited states or directions.

Time Complexity: O(N²)
Space Complexity: O(1) (excluding output array)

class Solution {
public:
  vector<vector<int>> generateMatrix(int n) {
      vector<vector<int>> res(n, vector<int>(n));
      int top = 0, bottom = n - 1, left = 0, right = n - 1, num = 1;

      while (top <= bottom && left <= right) {
          for (int i = left; i <= right; i++) res[top][i] = num++;
          top++;
          for (int i = top; i <= bottom; i++) res[i][right] = num++;
          right--;
          for (int i = right; i >= left; i--) res[bottom][i] = num++;
          bottom--;
          for (int i = bottom; i >= top; i--) res[i][left] = num++;
          left++;
      }
      return res;
  }
};

8. Rotate Image

Explanation: Rotate an n x n 2D matrix by 90 degrees clockwise in-place.

🐢 Brute Force

Create a new dummy matrix of the same size. Copy elements such that the first row of the original matrix becomes the last column of the new matrix. Finally, overwrite the original matrix.

Space Complexity: O(N²)

class Solution {
public:
  void rotate(vector<vector<int>>& matrix) {
      int n = matrix.size();
      vector<vector<int>> res(n, vector<int>(n));
      for(int i = 0; i < n; i++){
          for(int j = 0; j < n; j++){
              res[j][n - i - 1] = matrix[i][j];
          }
      }
      matrix = res;
  }
};

🚀 Optimal Approach

Achieve O(1) space complexity by rotating the matrix mathematically in two steps:

Transpose the matrix (swap matrix[i][j] with matrix[j][i]).
Reverse each row.

Time Complexity: O(N²)
Space Complexity: O(1)

class Solution {
public:
  void rotate(vector<vector<int>>& matrix) {
      int n = matrix.size();
      // Step 1: Transpose
      for (int i = 0; i < n; i++) {
          for (int j = i; j < n; j++) {
              swap(matrix[i][j], matrix[j][i]);
          }
      }
      // Step 2: Reverse each row
      for (int i = 0; i < n; i++) {
          reverse(matrix[i].begin(), matrix[i].end());
      }
  }
};

9. Trapping Rain Water

Explanation: Given an elevation map representing bars of width 1, compute how much water it can trap after raining. The water above any bar is determined by min(max_left_height, max_right_height) - current_height.

🐢 Brute Force

For every single bar, loop to its left to find the maximum height, and loop to its right to find the maximum height.

Time Complexity: O(N²)

class Solution {
public:
  int trap(vector<int>& h) {
      int n = h.size(), res = 0;
      for(int i = 0; i < n; i++){
          int lmax = 0, rmax = 0;
          for(int j = 0; j <= i; j++) lmax = max(lmax, h[j]);
          for(int j = i; j < n; j++) rmax = max(rmax, h[j]);
          res += min(lmax, rmax) - h[i];
      }
      return res;
  }
};

🚀 Optimal Approach

Use the Two Pointers technique. Maintain a left pointer and a right pointer, along with left_max and right_max. Process the smaller of the two max heights, as it guarantees the minimum boundary for trapped water.

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

class Solution {
public:
  int trap(vector<int>& height) {
      int left = 0, right = height.size() - 1;
      int left_max = 0, right_max = 0;
      int water = 0;
      
      while (left < right) {
          if (height[left] < height[right]) {
              height[left] >= left_max ? (left_max = height[left]) : water += (left_max - height[left]);
              left++;
          } else {
              height[right] >= right_max ? (right_max = height[right]) : water += (right_max - height[right]);
              right--;
          }
      }
      return water;
  }
};

10. Median of Two Sorted Arrays

Explanation: Find the median of two sorted arrays nums1 and nums2. The overall run time complexity should be O(log (m+n)).

🐢 Brute Force

Merge both sorted arrays into a new combined array, sort it (or merge properly like merge sort to avoid sorting), and return the middle element(s).

Time Complexity: O(N + M)
Space Complexity: O(N + M)

class Solution {
public:
  double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
      vector<int> v;
      v.insert(v.end(), a.begin(), a.end());
      v.insert(v.end(), b.begin(), b.end());
      sort(v.begin(), v.end());

      int n = v.size();
      if(n % 2) return v[n / 2];
      return (v[n / 2 - 1] + v[n / 2]) / 2.0;
  }
};

🚀 Optimal Approach

Use Binary Search on the smaller array to partition both arrays such that the left half has the same number of elements as the right half, and all elements on the left are smaller than the elements on the right.

Time Complexity: O(log(min(N, M)))
Space Complexity: O(1)

class Solution {
public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
      if (nums1.size() > nums2.size()) {
          return findMedianSortedArrays(nums2, nums1);
      }
      
      int x = nums1.size();
      int y = nums2.size();
      int low = 0, high = x;
      
      while (low <= high) {
          int partitionX = (low + high) / 2;
          int partitionY = (x + y + 1) / 2 - partitionX;
          
          int maxLeftX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
          int minRightX = (partitionX == x) ? INT_MAX : nums1[partitionX];
          
          int maxLeftY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
          int minRightY = (partitionY == y) ? INT_MAX : nums2[partitionY];
          
          if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
              if ((x + y) % 2 == 0) {
                  return ((double)max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2;
              } else {
                  return (double)max(maxLeftX, maxLeftY);
              }
          } else if (maxLeftX > minRightY) {
              high = partitionX - 1;
          } else {
              low = partitionX + 1;
          }
      }
      return 0.0;
  }
};

🚀 Final Thoughts

👉 Don’t just read — solve these problems yourself. Check out the brute force first, understand why it's slow, and implement the optimal approach to master the underlying patterns.