Session 4: Implementation Lab, Arrays, Maths, 1D 2D

Original Session

Date: 7 Nov 2024

• 268. Missing Number
  • leetcode here

    private int missingBySwapping(int[] nums) {
    
            int i = 0;
            int n = nums.length;
    
            while ( i < n) {
    
                int correctIndex = nums[i];
    
                if (i != nums[i] && nums[i] < n) {
    
                    int temp = nums[i];
                    nums[i] = nums[correctIndex];
                    nums[correctIndex] = temp;
                    continue;
                }
    
                i++;
            }
    
            for (int index = 0; index<n; index++) {
                if (nums[index] != index) {
                    return index;
                }
            }
    
            return n;
        }

• 448. Find All Numbers Disappeared in an Array
  • leetcode here
    
    

    public List<Integer> findDisappearedNumbers(int[] nums) {
            
            int n = nums.length;
            int i = 0;
    
            while ( i < n) {
    
                int correctIndex = nums[i] - 1;
    
                if (correctIndex + 1 != nums[correctIndex]) {
                    int temp = nums[correctIndex];
                    nums[correctIndex] = nums[i];
                    nums[i] = temp;
                    continue;
                }
                i ++;
            }
    
            List<Integer> list = new ArrayList();
            for (int index = 0; index < n; index ++) {
                
                if (nums[index] != index + 1) {
                    list.add(index + 1);
                }
            }
    
            return list;
        }

• 645 . Set Mismatch
  • leetcode here

    public int[] findErrorNums(int[] nums) {
            
            int n = nums.length;
            int i = 0;
    
            while (i < n) {
    
                int correctIndex = nums[i] - 1;
    
                if (nums[i] == nums[correctIndex]) {
                        i ++;
                        continue;
                }
    
                int temp = nums[correctIndex];
                nums[correctIndex] = nums[i];
                nums[i] = temp;
            }
    
            List<Integer> list = new ArrayList();
            for (int index = 0; index < n; index ++) {
    
                if (nums[index] != index + 1) {
                    list.add(nums[index]);
                    list.add(index + 1);
                }
            }
    
            return list.stream().mapToInt(Integer::intValue).toArray();
        }

• 442. Find All Duplicates in an Array
  • leetcode

    public List<Integer> findDuplicates(int[] nums) {
            
            int n = nums.length;
            int i = 0;
    
            while (i < n) {
    
                int correctIndex = nums[i] - 1;
    
                if (nums[i] == nums[correctIndex]) {
                        i ++;
                        continue;
                }
    
                int temp = nums[correctIndex];
                nums[correctIndex] = nums[i];
                nums[i] = temp;
            }
    
            List<Integer> list = new ArrayList();
            for (int index = 0; index < n; index ++) {
    
                if (nums[index] != index + 1) {
                    list.add(nums[index]);
                }
            }
    
            return list;
        }

• 287. Find the Duplicate Number
  • leetcode

    Input: nums = [1,3,4,2,2]
    Output: 2
    
    public int findDuplicate(int[] nums) {
            
            int n = nums.length;
    
            int[] newArr = new int[n];
    
            for (int index = 0; index < n; index ++) {
                int newIndex = nums[index] - 1;
                if (newArr[newIndex] == 1) {
                    return newIndex + 1;
                } else {
                    newArr[newIndex] = 1;
                }
            }
            return n;
        }

• 41. First Missing Positive
  • code

    public int firstMissingPositive(int[] nums) {
    
         int n = nums.length;
         int i = 0;
    
         while (i < n) {
            
            int correctIndex = nums[i] - 1;
    
            if (nums[i] > 0
            && nums[i] <= n
            && nums[i] != nums[correctIndex]) {
    
                int temp = nums[correctIndex];
                nums[correctIndex] = nums[i];
                nums[i] = temp;
                continue;
            }
    
            i++;
         }  
    
         for (int index = 0; index < n; index ++) {
            
            if (nums[index] != index + 1) {
                return index + 1;
            }
         }
    
         return n + 1;
    
        }

• 189. Rotate Array
  • rotate right (rotate left = opposite of rotate right.)
  • Rotate left partition, rotate right partition, in the end rotate entire array
  • leetcode here

    public void rotate(int[] nums, int k) {
            
            int arrSize = nums.length;
            k = k%arrSize;
    
            
            reverse(nums, 0, nums.length-1-k);
            reverse(nums, nums.length-k, nums.length-1);
            reverse(nums, 0, nums.length-1);
        }
    
        private void reverse(int[] nums, int low, int high) {
    
            while (low < high) {
                int temp = nums[low];
                nums[low] = nums[high];
                nums[high] = temp;
                low ++;
                high --;
            }
        }