Java solution with integers encode trick explained


  • 10
    A

    This is not the most concise solution but it has one trick that may be useful for many beginners that allows to encode two integers into one with possibility to decode it to both integers back. Once you know it you will always use it as it allows to avoid tuples of integers (as java lacks such structure in its libraries) and use just one integer to represent two.

    So, if we have two integers k and m and m is always less than some n - we can encode both into one integer using formula:

    r = k * n + m
    (m < n)
    

    and now to retrieve them use the following:

    k = r / n
    m = r % n
    

    And just to repeat: this trick is possible only if m is strictly less than n

    Using this trick we can solve many interview tasks that require constant space and have some array which contains integers less than size or array n. If this array requires some extra information for every item, but we cannot loose the initial item value - this can be solved either creating new array (simple) or just encoding initial value and new value directly in the array.

    Turning back to the task:

    We want to "seriallize" all values to their indices. So "1" will come to nums[0], "2" - nums[1] etc. After this we can easily find the "gap". This is an easy task if we could use extra memory for another array. But we cannot. So we can use the "encoding" scheme offered above:

    1.clean every non-relevant item from the array to match the restriction m < n:

    int n = nums.length;
    for (int i = 0; i < n; i++) {
         if (nums[i] <= 0 || nums[i] > n) nums[i] = 0;
    }
    

    2.Encode all items to their matching positions:

    int m = n + 1;
    for (int i = 0; i < n; i++) {
        // retrieve the value that initially was at index i (it could be overwritten by encoding)
        int prev = nums[i] % m;
        if (prev > 0) 
            // encode it using formula k * n + m, where for 'm' we also use decoding schema
            nums[prev - 1] = (prev * m) + nums[prev - 1] % m;
    }
    

    3.Find the gap:

    for (int i = 0; i < n; i++) {
        if (nums[i] / m != i + 1) return i + 1;
    }
    

    All in one:

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int m = n + 1;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) nums[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            int prev = nums[i] % m;
            if (prev > 0) 
                nums[prev - 1] = (prev * m) + nums[prev - 1] % m;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] / m != i + 1) return i + 1;
        }
        return m;
    }

  • 0
    Y

    Should it be m = r % n instead of m = r % m?


  • 0
    K

    i think so too


  • 0
    A

    thank you guys, I corrected it


  • 0
    S

    @anton4 Thank you for sharing this trick. Can you suggest some other leetcode question where you used this trick or this trick could come handy? I have seen something similar been done for encoding a 2d-array index (i,j) to a number as i*n+j.


  • 0
    A

    @SM54 not sure you still need my answer but one of the examples would be the type of tasks which works with grids (int[][]) and traverses them. If you need to keep the visited cells one option is to have boolean[][] array which would take n*m memory. Instead of it you can use Set<Integer> and encode the coordinates in it during write and check. See "Spiral Matrix" task as the example
    Another example is https://discuss.leetcode.com/topic/50837/the-most-concise-java-solution-possible-beats-99-with-explanation - I used this idea to encode number positions into the array before sorting, thus I used O(1) memory to solve the problem


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.