there are two questions both where LC Easy to Medium.

Time -> 60 mins.

  1. Encrypt the string : you will be given a string and you need to encrypt it
    Rules : substring "aaaa" should encrypt as "a4"
    "a" as "a"
    Simply if "abaasass" then encrypted string is "aba2sas2".

    Approach : simple traversal with window look for if there is continous substring with single character if it there count the number of
    character and increment the pointer.
    and add the the result string.

    Time Complexity : O(n)
    Space Complexity : O(n) -> in worst case

  2. Find kth smallest missing from given array.
    given an array of integer and a integer k you need to find the kth smallest missing number from array.
    consider smallest number start from 1.
    return and k datatype is long.

    Constraints : 1<= arr.length <= 2* 1e5
    1 <= arr[i] <= 1e9
    1<= k <= 1e12

    as constraints was large we can't think of priority_queue or loop traversal.
    Approach : I look at given array sort it then try to get the differnece between consecutive element( difference = arr[i]-arr[i-1] )
    and subtract it from k. (get the number of element which are not present in array and subtract it from k) at any moment my
    difference is greater then k then just return arr[i-1]+k; or atlast just return arr[n-1]+k;

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

Able to Solve Both Problems in time may be in minimum time.

image

Interested people can join for updates on
leetcode daily problem and contest discussion : group

Comments (4)