Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Java Solution : O(n) space and O(n) time complexity

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public boolean hasCycle(ListNode head) {

        Set<ListNode> nodeSeen = new HashSet<>();

        while(head !=null){

            if(nodeSeen.contains(head))

                return true;

            else

                nodeSeen.add(head);

            head=head.next;

        }

        return false;

    }

}

Java Solution : O(n) Time Complexity O(1) Space Complexity

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public boolean hasCycle(ListNode head) {

        ListNode fast = head;

        ListNode slow = head;

        while(fast!=null&&fast.next!=null){

            slow = slow.next;

            fast = fast.next.next;

            if(slow==fast)

                return true;

        }

        return false;

    }

}

ValueError: need more than 2 values to unpack

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: need more than 2 values to unpack

Solution :

No of variables should be equal to no of elements in sequence or tuple.

Example :

data = [25,"Satya","G",(8,31,2010)]
age,fname,lname,dob = data
print("My name ",fname+lname," and age ",age," dob ",dob)
age,fname,lname,(month,day,year) = data
print("My name ",fname+lname," and age ",age," and year i born :",year)

Single Number - LeetCode

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

Java Solution :

class Solution {
    public int singleNumber(int[] nums) {
        if(nums == null) return 0;
        int result = 0;
        for(int i=0;i<nums.length;i++){
            result ^= nums[i];
        }
        return result;
    }
}

Pascal's Triangle II - LeetCode

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3
Output: [1,3,3,1]

Java Solution :

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>();
        result.add(1);
        if(rowIndex == 0)
            return result;
        for(int i = 1; i <=  rowIndex ; i++){
            for(int j = i-1;j > 0; j--){
                result.set(j,result.get(j-1)+result.get(j));
            }
            result.add(1);
        }
        return result;
    }
}

Pascal's Triangle - LeetCode

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Java Solution :

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(numRows == 0)
           return result;
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        result.add(row);
        for(int i=1;i<numRows;i++){
            List<Integer> prevRow = new ArrayList<Integer>();
            prevRow = result.get(i-1);
            row = new ArrayList<>();
            row.add(1);
            for(int j=1 ; j < i ; j++){
                row.add(prevRow.get(j-1)+prevRow.get(j));
            }
            row.add(1);
          result.add(row);
        }
        return result;
    }
}

Time Complexity : O(n*n)

Space Complexity : O(n*n)

Data Structures and Algorithms Tutorial

Why Sorting ?

Sorting is  used to order the elements or data in increasing or decreasing order or in lexicographical order.

More than 25% of time spent on sorting in computing .

Use Cases :

1. For searching , sorting is a kind of pre-computation done on data. So that element can be easily found.

2. Sorting is used to find duplicates in a group of elements.

   i.e when you sort all the elements will be in order and duplicate elements will be next to each other and easily be found. (Duplicates will be in consecutive)

3. Matching items in two files . When you sort the two files and matching items can be easily found in single pass.

   i.e This can be implemented using merge sort.

4. Median can be easily when sorted.

    i.e After sorted middle element will be the median.

5. Top K minimum or maximum elements.

6.  Truncated top of items that are relevant to our search.

Ex : Facebook feed , Google search , Gmail search , Twitter feed , Instagram feed , Airbnb homes search , Amazon search bar results.


Main Usage :

1. How to attack new problems .

Algorithm design strategies like Divide and Conquer and Decrease and Conquer.

2.  To analyse algorithms to determine their performance. So that you can choose between two competing solutions of a problem.

Brute Force Design Strategy :

Brute Force is a simplest and straight forward design strategy based up on the problem statement.

Selection Sort :

Selection sort means iterate over the unsorted array and find the minimum element and place it in it's right position.

An algorithm efficiency is determined by it's time and space complexity.

Selection sort Algorithm :

Java Solution :

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Java Solution : Selection Sort

class Solution {

    public List<Integer> sortArray(int[] nums) {

        List<Integer> sortedList = new ArrayList<>();

        for(int i = 0; i < nums.length;i++){

            int minimumValueIndex = i;

            for(int j=i+1; j < nums.length;j++){

                if(nums[j] < nums[minimumValueIndex]){

                    minimumValueIndex = j;

                }

            }

            if(i != minimumValueIndex){ // To skip this loop when elements at both indexes are equal.

                int temp = nums[i];

                nums[i] = nums[minimumValueIndex];

                nums[minimumValueIndex] = temp;

            }

        }   

        for(int i=0;i < nums.length;i++){

            sortedList.add(new Integer(nums[i]));

        }

        return sortedList;

    }

}



Time Complexity : O(n*n) because two for loops.

Space Complexity : O(n) space for LinkedList

Bubble Sort :

Java Solution : Bubble Sort

class Solution {

    public List<Integer> sortArray(int[] nums) {

        // Bubble Sort

        // In bubble sort we will iterate from right to left and bubble up if we find any right element is less than it's left element and in each iteration minimum element will come to it's position.

        // Bubble sort is a variant of brute force approach.

        List<Integer> sortedList = new ArrayList<>();

        int temp = 0;

        for(int i = 1 ;i < nums.length;i++){

            for(int j = nums.length-1; j > 0 ; j--){

                if(nums[j-1] > nums[j]){

                    temp = nums[j];

                    nums[j] = nums[j-1];

                    nums[j-1] = temp;

                }

            }

        }

        for(int num : nums){

            sortedList.add(new Integer(num));

        }

        return sortedList;

    }

}

Time Complexity : O(n*n) n is no fo iterations . other n for number of swaps.

Space Complexity : O(n)

 

LeetCode - House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

Java Solution :

class Solution {

    public int rob(int[] nums) {

        // if we have only one house . He can rob only one house

        // if we two houses . He can max of the two houses.

        // if three houses . he can rob 3rd and add to 1st house. But if second half alone can have // //more. so have to choose max of both. Max(2nd house , 1st house + 3rd house)

        // 

        int premax = 0;

        int prepremax = 0;

        int maxrob = 0;

        for(int i=0;i<nums.length;i++){

            nums[i] = Math.max(nums[i]+prepremax,premax); // main thing here is to form the base case.

            prepremax = premax;

            premax = nums[i];

            maxrob = Math.max(maxrob,nums[i]);

        }

        return maxrob;

    }

}

Time Complexity : O(n)

Space Complexity : O(1)