Coding Interview Questions With Solutions: array

Showing posts with label array. Show all posts

Saturday, 12 February 2022

Product of Array Except Self

Krishna Chaurasia array, geeksforgeeks, interview, leetcode, programming 5 comments

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Approach:

The idea is to traverse the array couple of times from left to right once and right to left once keeping track the accumulated product so far from both the sides.

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
vector<int> productExceptSelf(vector<int> &nums) {
    int numsSize = nums.size();
    vector<int> result(numsSize);
    int temp = 1;
    // stores the product on the left of each element excluding itself
    for(int i = 0; i < numsSize; i++){
        result[i] = temp;
        temp = temp * nums[i];
    }
    temp = 1;
    // stores the product on the left times product on right of each element excluding itself
    for(int i = numsSize - 1; i >= 0; i--){
        result[i] = result[i] * temp;
        temp = temp * nums[i];
    }
    return result;
}

Move Zeros

Krishna Chaurasia array, interview, leetcode, segregate 2 comments

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

void moveZeroes(int* nums, int numsSize){
    int i = 0, j = 0;
    for(i = 0; i < numsSize; i++){
        //copy non-zero elements
        if(nums[i] != 0){
            nums[j] = nums[i];
            j++;
        }
    }
    //put zeros in the end
    while(j < numsSize){
        nums[j++] = 0;
    }
}

Find Peak Element

Krishna Chaurasia array, binary search, geeksforgeeks, interview, leetcode 7 comments

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Approach: Use binary search.

int peakIndex(int *arr, int low, int high){
    if(low == high){
        return low;
    }
    if(low + 1 == high){
        if(arr[low] >= arr[high]){
            return low;
        }else{
            return high;
        }
    }
    int mid = (low + high) / 2;
    if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]){
        return mid;
    }else if(arr[mid] < arr[mid - 1]){
        //peak lies on the left since arr[mid - 1] > arr[mid] && arr[0] = -infinity so there has to be an element which is peak on the left
        return peakIndex(arr, low, mid - 1);
    }else{
        //peak lies on the right
        return peakIndex(arr, mid + 1, high);
    }
}

int findPeakElement(int* nums, int numsSize) {
    return peakIndex(nums, 0, numsSize - 1);
}

Leaders in an array

Krishna Chaurasia array, geeksforgeeks, leader 1 comment

An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader.
For example int the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.

#include <iostream>
using namespace std;

int main(){
    int arr[] = {18, 16, 17, 4, 3, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxSoFar = arr[n - 1];
    cout << maxSoFar << " ";
    for(int i = n - 2; i >= 0 ; i--){
        if(arr[i] > maxSoFar){
            cout << arr[i] << " ";
            maxSoFar = arr[i];
        }
    }
    cout << endl;
    return 0;
}

283. Move Zeroes

Krishna Chaurasia array, interview, leetcode, programming No comments

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Approach: Bring forward the non-zero values using a for loop and then fill the zeros at the end.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j = 0, n = nums.size();
        //move the non-zero elements to the front
        for(int i = 0; i < n; i++){
            if(nums[i] != 0){
                nums[j++] = nums[i];
            }
        }
        //fill the remaining right indices with zeros
        for(int i = j; i < n; i++){
            nums[i] = 0;
        }
    }
};

Here is the link to the ideone solution : http://ideone.com/O0MRQa

53. Maximum Subarray

Krishna Chaurasia array, geeksforgeeks, interviewbit, Kadene's algorithm, leetcode, maximum sum No comments

Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Approach : Kadene's Algorithm


def max_subarray(A):
max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Source: Wikipedia

Solution:

int maxSubArray(int* nums, int numsSize) {
    int curSum, maxSum = INT_MIN;
    curSum = 0;
    for(int i = 0; i < numsSize; i++){
        curSum = curSum + nums[i];
        if(curSum > maxSum){
            maxSum = curSum;
        }
        if(curSum < 0){
            curSum = 0;
        }
    }
    return maxSum;
}

Here is the link to the ideone solution : http://ideone.com/howey4

1. Two Sum

Krishna Chaurasia array, hash map, interview, leetcode, programming No comments

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

Example:



Given nums = [2, 7, 11, 15], target = 9,





Return [0, 1] since nums[0] + nums[1] = 2 + 7 = 9

Approach:

The brute force solution is to use two loops and find the two indices. The time complexity of this solution is O(n ^ 2)

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        int n = nums.size();
        for(int i = 0; i < n - 1; i++){
            for(int j = i + 1; j < n; j++){
                if(nums[i] + nums[j] == target){
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
        }
        return result;
    }
};

A time efficient solution would be to use hash maps and find the two numbers in O(n) time assuming hash maps take O(1) time.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> indexMap;
        vector<int> result;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(indexMap.find(target - nums[i]) != indexMap.end()){
                result.push_back(indexMap[target - nums[i]]);
                result.push_back(i);
                return result;
            } else{
                indexMap[nums[i]] = i;
            }
        }
        return result;
    }
};

Here is the ideone link for the solution: 2 Sum : http://ideone.com/O74qFR

Four Sum

Krishna Chaurasia array, geeksforgeeks, interview, leetcode, sorting No comments

Given an array of integers, find all combination of four elements in the array whose sum is equal to a given value X.

Idea :
1) Find all pair sum, requires O(n^2) space
2) Sort the pair sum.
3) Find the 4 elements(2 pairs) using the approach in two pair sum solution in O(n^2) time.

#include <iostream>
using namespace std;

struct pairSum{
    int sum, first, second;
};

void findPairSum(int *arr, struct pairSum *temp, int n){
    int k = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            temp[k].sum = arr[i] + arr[j];
            temp[k].first = arr[i];
            temp[k].second = arr[j];
            k++;
        }
    }
}

void merger(struct pairSum *arr, struct pairSum *temp, int low, int mid, int high){
    int i = low, j = mid + 1, k = low;
    while(i <= mid && j <= high){
        if(arr[i].sum <= arr[j].sum){
            temp[k].sum = arr[i].sum;
            temp[k].first = arr[i].first;
            temp[k].second = arr[i].second;
            k++;
            i++;
        } else{
            temp[k].sum = arr[j].sum;
            temp[k].first = arr[j].first;
            temp[k].second = arr[j].second;
            k++;
            j++;
        }
    }
    while(i <= mid){
        temp[k].sum = arr[i].sum;
        temp[k].first = arr[i].first;
        temp[k].second = arr[i].second;
        k++;
        i++;
    }
    while(j <= high){
        temp[k].sum = arr[j].sum;
        temp[k].first = arr[j].first;
        temp[k].second = arr[j].second;
        k++;
        j++;
    }
    for(int i = low; i<= high; i++){
        arr[i].sum = temp[i].sum;
        arr[i].first = temp[i].first;
        arr[i].second = temp[i].second;
    }
}

void mergeSort(struct pairSum *arr, struct pairSum *temp, int low, int high){
    if(low < high){
        int mid = (low + high) / 2;
        mergeSort(arr, temp, low, mid);
        mergeSort(arr, temp, mid + 1, high);
        merger(arr, temp, low, mid, high);
    }
}

void find4Numbers(struct pairSum *arr, int sz, int x){
    struct pairSum *sorted = new pairSum[sz];
    int l = 0, r = sz - 1, sum;
    mergeSort(arr, sorted, 0, sz - 1);
    while(l < r){
        sum = sorted[l].sum + sorted[r].sum;
        if(sum == x && (sorted[l].first != sorted[r].first && sorted[l].first != sorted[r].second
                        && sorted[l].second != sorted[r].first && sorted[l].second != sorted[r].second)){
            cout << "Four elements : " << sorted[l].first << ", " << sorted[l].second << ", " << sorted[r].first << ", " << sorted[r].second << endl;
            return;
        } else if(sum > x){
            r--;
        } else{
            l++;
        }
    }
    cout << "No 4 elements found!" << endl;
    return;
}


int main(){
    int arr[] = {1, 4, 45, 6, 10, 12};
    int x = 56;
    int n = sizeof(arr)/sizeof(arr[0]);
    int sz = n * (n - 1) / 2;
    struct pairSum *pairSums = new struct pairSum[sz];
    findPairSum(arr, pairSums, n);
    find4Numbers(pairSums, sz, x);
    return 0;
}

Single Number

Krishna Chaurasia array, bitwise, geeksforgeeks, interview, interviewbit, xor 19 comments

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.

Example:
I/P = [1, 2, 3, 2, 3, 1, 3]
O/P = 3

Approach: Take xor of all the elements. The number of terms occurring even number of times get cancelled due to property of xor that a ^ a = 0

#include<iostream>
using namespace std;

int main(){
    int arr[] = {2, 3, 3, 3, 3, 4, 2, 4, 4, 2, 4}; //{1, 2, 4, 4, 10, -8};

    int n = sizeof(arr)/sizeof(arr[0]);
    int result = 0;
    for(int i = 0 ; i < n ; i++ ){
        result = result ^ arr[i];
    }
    cout << result << " is the odd time occurring element!" << endl;
    return 0;
}

Range Sum Query - Immutable

Krishna Chaurasia array, interview, leetcode, vector 2 comments

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

You may assume that the array does not change.
There are many calls to sumRange function.

Approach: Compute the sum till all the ith index in the array for all 0 <= i < n. Use this precomputed values to return the sum.

class NumArray {
public:
    vector<int> array;
    vector<int> sum;
    NumArray(vector<int> &nums) {
        for(int i = 0 ; i < nums.size(); i++){
            array.push_back(nums[i]);
        }
        //preProcess after the vector is initialized
        preProcess();
    }
    
    //preProcess to store the sum till all i in a vector since the function is called many times
    void preProcess(){
        sum.push_back(0);
        for(int i = 1; i <= array.size(); i++){
            sum.push_back(sum[i - 1] + array[i - 1]);
        }
    }

    int sumRange(int i, int j) {
        //return sum directly from the calculated sums
        int res = sum[j + 1] - sum[i];
        return res;
    }
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

Largest Number

Krishna Chaurasia array, geeksforgeeks, interviewbit, sorting No comments

Given a list of non-negative integers, return the largest number that can be formed by their arrangement.

Eg. For the list [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Approach: We need sorting but in the modified way since if we have the number 9, 80 in the list then the largest number can be 980 but sorting will give 809. So, we modify sorting such that the for the pair(X, Y) in the list X comes first after sorting if XY > YX where XY represents concatenation of X and Y. Thus, for 9, 80, we will have the sorting result as 980 since 980 > 809.

int myCompare(int a, int b){
    string X = to_string(a);
    string Y = to_string(b);
    string XY = X.append(Y);
    string YX = Y.append(X);
    return XY.compare(YX) > 0 ? 1 : 0;
}

string Solution::largestNumber(const vector<int> &A) {
    vector<int> temp(A);
    string result =  "";
    int count = 0;
    for(int i = 0 ; i < A.size(); i++){
        if(A[i] == 0){
            count++;
        }
    }
    //handling all 0 vector
    if(count == A.size()){
        result = "0";
        return result;
    }
    //sort as per modified compare function
    sort(temp.begin(), temp.end(), myCompare);
    
    string out = "";
    //make a string for the result
    for(int i = 0; i < A.size(); ++i){
        result.append(to_string(temp[i]));
    }
    return result;
}

Majority Element in a Sorted Array

Krishna Chaurasia array, binary search, geeksforgeeks, majority element, sorted array 2 comments

Write an algorithm to find if a given integer x appears more than n/2 times in a sorted array of n integers. See this for a similar problem on Majority Element.

Approach: Use binary search to find the first occurrence of x in the array.
TC = O(log(n))

#include <iostream>
#include <cmath>
using namespace std;

int binsrch(int *arr, int x, int low, int high){
    if(low <= high){
        int mid = (low + high) / 2;
        // returns the first occurrence of x
        if(arr[mid] == x && (arr[mid] > arr[mid - 1] || mid == 0)){
           return mid;
        }
        if(x > arr[mid]){
            return binsrch(arr, x, mid + 1, high);
        } else{
            return binsrch(arr, x, low, mid - 1);
        }
    }
    return -1;
}

int isMajority(int *arr, int x, int n){
    int first = binsrch(arr, x, 0, n - 1);
    if(first == -1){
        return 0;
    }
    if((first + n/2) <= (n - 1) && arr[first + n/2] == x){
        return 1;
    }
    return 0;
}

using namespace std;

int main(){
    int arr[] ={1, 2, 3, 4, 4, 4, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 4;
    if(isMajority(arr, x, n)){
        cout << x << " is the majority element." << endl;
    } else{
        cout << x << " is not the majority element." << endl;
    }

    return 0;
}

Majority Element

Krishna Chaurasia array, frequency, geeksforgeeks, majority element, Moore's Voting No comments

Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Idea : To find the majority element using Moore's Voting Algorithm

Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

#include<iostream>
using namespace std;

int main(){
    int arr[] = {2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 2, 4, 4}; //{1, 2, 4, 4, 10, -8};

    int n = sizeof(arr)/sizeof(arr[0]);
    int count,  majorityElt;
    majorityElt = arr[0];
    count = 1;
    for(int i = 1 ; i < n ; i++ ){
        if(arr[i] == majorityElt){
            count++;
        } else {
            count--;
        }
        if(count == 0){
            count = 1;
            majorityElt = arr[i];
        }
    }
    count = 0;
    for(int i = 0 ; i < n ; i++){
        if(arr[i] == majorityElt){
            count++;
        }
    }
    if(count > n/2){
        cout << majorityElt << " is the majority element " << endl;
    } else{
        cout << "No such element exists" << endl;
    }
    return 0;
}

Two Sum Zero

Krishna Chaurasia array, geeksforgeeks, programming 4 comments

An array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero.

Approach : Using the approach given in the 2 Sum post.

#include <iostream>
#include <cmath>
using namespace std;

void mergeSort(int *, int, int);
void merger(int *, int, int, int);
void sumToZero(int *, int);

void sumToZero(int *arr, int n){
    int i = 0, j = n - 1, sum, minSum, minLeft, minRight;
    minSum = 999999;
    minLeft = i;
    minRight = j;
    while(i < j){
        sum = arr[i] + arr[j];
        if(abs(sum) > abs(minSum)){
            minSum = sum;
            minLeft = i;
            minRight = j;
        }
        if(sum < 0){
            i++;
        } else{
            j--;
        }
    }
    cout << "Elements whose sum is close to 0 : " << arr[minLeft] << " " << arr[minRight];
    cout << endl;
}

void mergeSort(int *arr, int low, int high){
    int mid;
    if(low < high){
        mid = (low + high)/2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merger(arr, low, mid, high);
    }
}

void merger(int *arr, int low, int mid, int high){
    int n1 = mid - low + 1;
    int n2 = high - mid;
    int left[n1], right[n2];
    int i, j, k;
    i = 0;
    while(i < n1){
        left[i] = arr[i + low];
        i++;
    }
    i = 0;
    while(i < n2){
        right[i] = arr[i + mid + 1];
        i++;
    }
    i = 0;
    j = 0;
    k = low;
    while(i < n1 && j < n2){
        if(left[i] <= right[j]){
            arr[k++] = left[i++];
        } else{
            arr[k++] = right[j++];
        }
    }
    while(i < n1){
        arr[k++] = left[i++];
    }
    while(j < n2){
        arr[k++] = right[j++];
    }
}

int main(){

    int arr[] = {1, 60, -10, 70, -80, 85};
    int n = sizeof(arr)/sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    sumToZero(arr, n);
    return 0;
}

Saturday, 12 February 2022

Product of Array Except Self

Monday, 4 October 2021

Move Zeros

Sunday, 12 September 2021

Find Peak Element

Thursday, 29 July 2021

Leaders in an array

Friday, 21 July 2017

283. Move Zeroes

Thursday, 20 July 2017

53. Maximum Subarray

Tuesday, 11 July 2017

1. Two Sum

Approach:

Tuesday, 6 June 2017

Four Sum

Sunday, 28 August 2016

Single Number

Range Sum Query - Immutable

Friday, 26 August 2016

Largest Number

Thursday, 25 August 2016

Majority Element in a Sorted Array

Wednesday, 24 August 2016

Majority Element

Two Sum Zero

Contact Me

Popular Posts

Categories

Blog Archive

| Privacy Policy | Disclaimer | Resume |

| Terms of Use | Contact Us | Site Map |