array‐cp‐questions

Table of Contents

1. XOR and Bit Manipulation
   • Count the Number of Bits to Flip to Convert A to B
2. Kadane's Algorithm
   • Maximum Subarray Sum (1D)
   • Maximum Subarray Sum (2D)
3. HashMap Problems
   • Longest Subarray with Sum Zero
4. Consecutive Sequences
   • Longest Consecutive Sequence
5. Merging Intervals
   • Merge Overlapping Intervals
6. Matrix Operations
   • Spiral Matrix Traversal
   • Matrix Rotation
7. Array Rearrangement
   • Rearrange Array Alternating Positive and Negative Elements
8. Profit Calculation
   • Max Profit by Buying and Selling Stock

---

XOR and Bit Manipulation

Count the Number of Bits to Flip to Convert A to B

Question: Given two integers, find how many bits need to be flipped to convert integer A to integer B.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int countBitsToFlip(int a, int b) {
        int xorValue = a ^ b;
        int count = 0;
        while (xorValue) {
            xorValue &= xorValue - 1;
            count++;
        }
        return count;
    }
};

int main() {
    Solution s;
    cout << s.countBitsToFlip(4, 6);
    return 0;
}

Explanation:

• The XOR operation between two numbers A ^ B identifies which bits are different.
• Brian Kernighan’s Algorithm (xorValue &= xorValue - 1) reduces the number of set bits, and the number of iterations is equal to the number of differing bits.
• This method efficiently counts how many bits differ between the two numbers.

---

Kadane's Algorithm

Maximum Subarray Sum (1D)

Question: Find the maximum sum of a contiguous subarray in a given 1D array.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxSubArraySum(vector<int>& arr) {
        int maxSum = 0, currentSum = 0;
        for (int num : arr) {
            currentSum += num;
            currentSum = max(currentSum, num);
            maxSum = max(maxSum, currentSum);
        }
        return maxSum;
    }
};

int main() {
    Solution s;
    vector<int> arr = {1, 7, -9, 8, 6};
    cout << s.maxSubArraySum(arr);
    return 0;
}

Explanation:

• Kadane's Algorithm is used here to find the maximum sum of a contiguous subarray.
• The algorithm iterates through the array, updating currentSum by including the current element or starting a new subarray from that element.
• The maxSum keeps track of the highest sum encountered.

Maximum Subarray Sum (2D)

Question: Find the maximum sum of a contiguous submatrix in a 2D array.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxSubArraySum1D(vector<int>& arr) {
        int maxSum = 0, currentSum = 0;
        for (int num : arr) {
            currentSum += num;
            currentSum = max(currentSum, num);
            maxSum = max(maxSum, currentSum);
        }
        return maxSum;
    }

    int maxSubMatrixSum2D(vector<vector<int>>& matrix) {
        int maxSum = 0;
        int rows = matrix.size(), cols = matrix[0].size();
        for (int left = 0; left < cols; ++left) {
            vector<int> temp(rows, 0);
            for (int right = left; right < cols; ++right) {
                for (int i = 0; i < rows; ++i) {
                    temp[i] += matrix[i][right];
                }
                maxSum = max(maxSum, maxSubArraySum1D(temp));
            }
        }
        return maxSum;
    }
};

int main() {
    Solution s;
    vector<vector<int>> matrix = {{1, 2, 3}, {3, -9, 4}, {3, -5, 8}};
    cout << s.maxSubMatrixSum2D(matrix);
    return 0;
}

Explanation:

• This is an extension of Kadane's Algorithm to 2D arrays.
• We iterate through all possible column pairs and treat each pair as a 1D array, finding the maximum subarray sum using the 1D Kadane’s Algorithm.

---

HashMap Problems

Longest Subarray with Sum Zero

Question: Find the length of the longest subarray with sum 0 in a given array.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestSubarrayWithZeroSum(vector<int>& arr) {
        unordered_map<int, int> sumIndexMap;
        int maxLength = 0, sum = 0;
        for (int i = 0; i < arr.size(); i++) {
            sum += arr[i];
            if (sum == 0) {
                maxLength = i + 1;
            }
            if (sumIndexMap.find(sum) != sumIndexMap.end()) {
                maxLength = max(maxLength, i - sumIndexMap[sum]);
            } else {
                sumIndexMap[sum] = i;
            }
        }
        return maxLength;
    }
};

int main() {
    Solution s;
    vector<int> arr = {15, -2, 2, -8, 1, 7, 10, 23};
    cout << s.longestSubarrayWithZeroSum(arr);
    return 0;
}

Explanation:

• The idea is to use a HashMap to store the sum at each index.
• If the same sum appears again, it means the subarray between the previous occurrence and the current index has a sum of 0.
• The algorithm checks for such subarrays and updates the maximum length accordingly.

---

Consecutive Sequences

Longest Consecutive Sequence

Question: Find the length of the longest consecutive elements sequence in an unsorted array.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestConsecutiveSequence(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int longestStreak = 0;
        for (int num : nums) {
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentStreak = 1;
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
};

int main() {
    Solution s;
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    cout << s.longestConsecutiveSequence(nums);
    return 0;
}

Explanation:

• This algorithm uses an unordered set to store the elements of the array.
• For each number, it checks if it is the start of a sequence by verifying if num - 1 exists.
• It then counts the consecutive sequence starting from that number and updates the maximum length.

---

Merging Intervals

Merge Overlapping Intervals

Question: Given a collection of intervals, merge all overlapping intervals.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        
        // Sort the intervals by their starting times
        sort(intervals.begin(), intervals.end());
        
        vector<vector<int>> merged;
        
        // Start with the first interval
        merged.push_back(intervals[0]);
        
        for (int i = 1; i < intervals.size(); i++) {
            // If the current interval overlaps with the last one in `merged`
            if (intervals[i][0] <= merged.back()[1]) {
                // Merge the current interval with the last interval in `merged`
                merged.back()[1] = max(merged.back()[1], intervals[i][1]);
            } else {
                // If no overlap, add the current interval to `

merged`
                merged.push_back(intervals[i]);
            }
        }
        
        return merged;
    }
};

int main() {
    Solution s;
    vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    vector<vector<int>> result = s.mergeIntervals(intervals);
    for (auto& interval : result) {
        cout << "[" << interval[0] << ", " << interval[1] << "] ";
    }
    return 0;
}

Explanation:

• The algorithm sorts the intervals by their starting points.
• It then iterates through the sorted intervals and merges any that overlap.
• Non-overlapping intervals are added to the result as is.

---

Matrix Operations

Spiral Matrix Traversal

Question: Given a matrix, traverse it in spiral order.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        if (matrix.empty()) return result;
        
        int top = 0, bottom = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;
        
        while (top <= bottom && left <= right) {
            // Traverse from left to right
            for (int i = left; i <= right; i++) {
                result.push_back(matrix[top][i]);
            }
            top++;
            
            // Traverse from top to bottom
            for (int i = top; i <= bottom; i++) {
                result.push_back(matrix[i][right]);
            }
            right--;
            
            if (top <= bottom) {
                // Traverse from right to left
                for (int i = right; i >= left; i--) {
                    result.push_back(matrix[bottom][i]);
                }
                bottom--;
            }
            
            if (left <= right) {
                // Traverse from bottom to top
                for (int i = bottom; i >= top; i--) {
                    result.push_back(matrix[i][left]);
                }
                left++;
            }
        }
        
        return result;
    }
};

int main() {
    Solution s;
    vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    vector<int> result = s.spiralOrder(matrix);
    for (int num : result) {
        cout << num << " ";
    }
    return 0;
}

Explanation:

• The algorithm uses four boundaries (top, bottom, left, right) to keep track of the edges of the matrix that need to be processed.
• It traverses the matrix in a spiral order by adjusting the boundaries and processing the elements accordingly.

Matrix Rotation

Question: Rotate a matrix 90 degrees clockwise.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

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

int main() {
    Solution s;
    vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    s.rotateMatrix(matrix);
    for (auto& row : matrix) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

Explanation:

• The algorithm first transposes the matrix by swapping matrix[i][j] with matrix[j][i].
• It then reverses each row to complete the 90-degree clockwise rotation.

---

Array Rearrangement

Rearrange Array Alternating Positive and Negative Elements

Question: Rearrange an array such that positive and negative numbers are alternated.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    void rearrangeArray(vector<int>& arr) {
        int n = arr.size();
        vector<int> result(n);
        int posIndex = 0, negIndex = 1;
        
        for (int num : arr) {
            if (num >= 0) {
                result[posIndex] = num;
                posIndex += 2;
            } else {
                result[negIndex] = num;
                negIndex += 2;
            }
        }
        
        arr = result;
    }
};

int main() {
    Solution s;
    vector<int> arr = {1, -2, 3, -4, 5, -6};
    s.rearrangeArray(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

Explanation:

• The algorithm uses two indices to place positive and negative numbers in the result array at alternating positions.
• The result array is then copied back to the original array.

---

Profit Calculation

Max Profit by Buying and Selling Stock

Question: Find the maximum profit by buying and selling a stock with a given list of prices.

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;
        
        for (int price : prices) {
            minPrice = min(minPrice, price);
            maxProfit = max(maxProfit, price - minPrice);
        }
        
        return maxProfit;
    }
};

int main() {
    Solution s;
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    cout << s.maxProfit(prices);
    return 0;
}

Explanation:

• The algorithm keeps track of the minimum price encountered and the maximum profit achievable based on that price.
• It iterates through the prices, updating the minimum price and maximum profit accordingly.

go up