Leetcode Practice

Today, we will work on some LeetCode questions to develop our approach to solving array problems.

---

Question 169: Majority Element

The question asks us to find the element that appears most frequently in an array called 'nums' of size n. There are multiple ways to solve this question, let’s see one by one.

Hashing Technique:

In this technique, we create an array that is one size larger than the given array. The size is determined by the highest value in the given array. For example, if we have an integer array[5] = {1, 3, 5, 4, 6}, we make a new array of size 7, because 6 is the highest value in the given array. In this new array, we count the frequency of the numbers present in the given array, with the numbers acting as the index of the new array. By doing this, we can sort and calculate the frequency in just O(n) time complexity using a single loop.

Code preview:

array[5] = {1, 3, 5, 4, 6};
hash_array[6+1] = {0};  // putting single 0 means all values are zero

for (int i = 0; i < 6;i++){
    hash_array[array[i]]++;   // increament the value present on index array[i]
}
for (int i = 0; i < 7; i++){
    if (hash_array[i] != 0){
    cout << i << hash_array[i]; // print number and its frequency
    }
}
// Time complexity will be order on 'n'or O(n)

Drawbacks of Hashing Technique:

• Memory Consuming (space complexity increased)

• No valid for negative numbers(index is not negative)

Boyer-Moore algorithm:

There is no issue with space or negative values when using the Boyer-Moore algorithm. To solve it, you need to use two variables: one for the result and one for the count. Start by assuming the first value in the array is the result and set the count to 1 (starting from 0). As you move to the next value in the array, if it matches the previous value, increase the count. If it doesn't match, decrease the count by 1. If the count reaches zero, update the result with the next value in the array and reset the count to 1. Repeat this process, and in the end, you will find your answer in the result.

int count = 1;
int result = array[0];

for (int i = 1; i < 5 ; i++){
    if(array[i] = result){
          count++
    }else{
    count--
    if(count == 0}{
    result = array[i]
    count = 1    }
    }
return result
}

Try to understand the code above on your own and think about the logic I shared in the figure above.

Question 283: Move Zeroes

The question asks us to separate the zeros from the array while keeping the relative order of the other elements the same. There are two ways to solve this problem: one is by swapping, and the other is by copying the values. Let's explore these two methods.

Swaping Technique:

The drawback of the swapping technique is that it does not maintain the relative order of the array.

Copying the non-zero value:

The best part of this logic is that the relative order stays the same.

CODE:

// assuming array name 'nums'
int zeroindex = 0;
for(int j = 0; j < nums.size(); j++){ // nums.size() is STL syntax
    if(num[j] != 0){
          nums[zeroindex++] = nums[j];     // increment the zeroindex syntax
            }
        }
// for making the next ALL element as ZERO again we have to make a for loop

for(  ; i < nums.size() ; i++){
    nums[i] = 0;  // assign the value as 0
}

Question 349: Intersection of Two Array

In this question, we need to create an array containing unique values from both given arrays, with no duplicate elements. This problem can be solved using two methods: the first is hashing, and the second is the initial thought that comes to mind for everyone.

Method (initial thought):

What I initially think is to check the elements of both arrays. If they are equal, then they will be part of the unique values. However, we also need to check whether that value is already present in our array. For this, I need to create another function that returns a boolean value, true or false. Let's see what I mean.

int array_one[i];     // size_one
int array_two[j];   // size_two
vector <int> result; // you can use vector to define array like this with unkown size

for (int i = 0; i < size_one; i++){
    for(int j = 0; j < size_two; j++){
        if(array_one[i] == array_two[j]){
            if ( !isPresent(array_one[i]) ) { // if not present
            copy(array_one[i])   // copy that, 
                }
           // i have written these two above line just in short , maybe syntax is wrong
            }
        }
    }
bool isPresent(int n){
    for(int i = 0; i < size ; i++){ // size of result array
           if( result[i] == n ){
                return true
                }    
             }
    return false  // if above 'if' not execute than this function will return false
    }

Method Hashing:

What we do is first calculate the frequency of elements from one of the arrays by creating a hash array, as done in the hashing technique. After that, we check the elements of the second array. If an element matches an index in the hash array with a non-zero value, it is unique, and we will add it to the result array.