Problems

Find Duplicate

Problem Statement: Given an array of n numbers, in the range 0 to n-1. Find if the array contains a duplicate

Approach:

1. Sort the array and iterate to check if any consecutive elements are equal. TC: O(log n)
2. Create a hash table. Check if an element already exists in the hash. TC: O(n), SC: O(n)
3. For each element A[i], update the element at index A[i] as negative of its value. If the element at index A[i] is already negative, then the A[i] is a duplicate

fun checkDuplicate(arr: IntArray) {
    for(i in 0 until arr.size) {
        if(A[abs(A[i])] < 0) {
            return true
        }
        else A[abs(A[i])] *= -1
    }
    return false
}

---

Max Repeated

Problem Statement: Given an array. Find the element which appears maximum number of times. Assume elements are in the range 0 to n-1

Approach:
In the first iteration add n to the value at index A[i]. In the second iteration find the index, i, at which (A[i] / n) is maximum. The \(i\) is the maximum repeated element.

fun maxRepeated(arr: IntArray) {
    for(i in 0 until arr.size) {
        A[A[i] % n] += n
    }
    var max = 0
    var maxI = 0
    for(i in 0 until arr.size) {
        if(A[i] /n > max) {
            max = A[i] / n
            maxI = i
        }
    }
    return maxI
}

---

Two Repeating

Problem Statement: Give an array of size n + 2, all the elements are in the range 1 to n. Find the two elements that are repeating.

Approach:
We can use XOR to solve this efficiently. XOR of all elements in the array and 1 to n, gives XOR of the repeated elements, X and Y. If the \(k^{th}\) bit of X XOR Y is 1, we can XOR all elements in the array and integers from 1 to n whose \(k^{th}\) bit is 1. The result will be X.

fun findRepeated(arr: IntArray) {
    var xor = 0
    arr.forEach { xor = xor xor it }
    (1 .. n).forEach{ xor = xor xor it }
    var rightMostBit = xor and (xor - 1).inv()
    var x = 0
    var y = 0
    arr.forEach {
        if(it and rightMostBit)  x = x xor it
        else y = y xor it
    }
    (1 .. n).forEach {
        if(it and rightMostBit)  x = x xor it
        else y = y xor it
    }
}

---

Find Sum Close to Zero

Problem Statement: Given an array. Find two elements whose sum is close to zero. Array contains both positive and negative integers

Approach:
Sort the array. Maintain 2 pointers, l and r. Also keep track of the smallest positive and largest negative sum. If A[l] + A[r]

• is greater than 0 and less than the smallest positive sum decrease j
• is less than 0 and greater than the largest negative sum increase i

---

Rotation point

Problem Statement: Given an array of n distinct integers. Suppose there exists an index k, such that A[1] ... A[k] is in increasing order and A[k + 1] ... A[n] is in decreasing order. Find k

Approach:
We can use a modified binary search to solve this efficiently

fun searchK(arr: IntArray) {
    var mid = 0
    var l = 0
    var r = arr.size - 1
    while(l <= r) {
        if(l == r) return l
        else if(l == r-1) {
            return if(A[l] > A[r]) l else r
        }
        else {
            mid = (l + r) / 2
            if(A[mid - 1] < A[mid] && A[mid] > A[mid + 1])
                return mid
            if(A[mid - 1] < A[mid] && A[mid] < A[mid + 1])
                l = mid + 1
            else r = mid - 1
        }
    }
}

---

Count Duplicates

Problem Statement: Given a sorted array. Find the number of occurrences of a given number.

Approach:

1. Linear search for first and last occurrence. TC: O(n)
2. Binary search for the first and last occurrence. TC: O(log n)

---

Majority Element

Problem Statement: An element is a majority if it appears more than n/2 times. Given an array find the majority element if its exists

Approach:

1. Use hash table to maintain count of each element. TC: O(n), SC: O(n)
2. Find median. If the median appears n/2 times. Then it is the majority element else no majority element.
3. Boyer-Moore majority vote algorithm:

fun majorityElement(arr: IntArray) {
    var count = 0
    var ele = -1
    arr.forEach {
        if(count == 0) {
            count = 1
            ele = it
        }
        else if(it == ele) count += 1
        else count--
    }
    // check if ele is repeated n/2 times
}

---

Binary Search n x n array

Problem Statement: Given an n x n array, such that each row and column are in ascending order. Find if an element x is in the array.

Approach:
Start with first column and last row. If A[1][n] < x skip the first column and if A[1][n] > x skip last row.

---

Separate even & odd

Problem Statement: Given an array. Modify the array such that all even comes first and then odd numbers.

Approach:
Maintain 2 pointers, move the left pointer until you find an odd number and right pointer until you find an even number. Swap them. Continue until the left pointer \(\le\) right pointer

fun evenOdd(arr: IntArray) {
    var l = 0
    var r = arr.size - 1
    while(l < r) {
        while(l < r && A[l] % 2 != 0) l++
        while(l < r && A[r] % 2 == 0 ) r--
        if( l < r) arr[l] = {
            arr[r].also { arr[r] = arr[l] }
            l++
            r--
        }
    }
}

---

Separate 0's and 1's

Problem Statement: Given an array of 1's and 0's. Modify the array so that 1's comes first and then 0's

Approach:
Same as above problem

---

Dutch National Flag Problem

Problem Statement: Given an array of 1's, 0's and 2's. Modify the array so that 0's comes first followed by 1's and then 2's

Approach:

fun dutchNationalFlag(arr: IntArray) {
    var l = 0
    var mid = 0
    var r = arr.size - 1
    while(mid <= high) {
        when(A[mid]) {
            0 -> {
                A[l] = A[mid].also { A[mid] = A[l] }
                l++
                mid++
            }
            1 -> {
                mid++
            }
            2 -> {
                A[mid] = A[r].also { A[r] = A[mid] }
                r--
            }
        }
    }
}

---

Problem Statement: Given an array. Find max j - i such that A[j] > A[i]

Approach:

---