📌Brute Force⏩Optimized⏩Queue👉interviewer Mindset
Intuition\n1. Brute force using loop iteration\n2. optimised using one loop\n3. Queue solution for more in depth\n\n# Approach\nWe find out min of tickets[i] an
# Intuition\n1. Brute force using loop iteration\n2. optimised using one loop\n3. Queue solution for more in depth\n\n# Approach\nWe find out min of tickets[i] and tickets[k]\n\n\n\n## Brute force approach\n- Time complexity: O(N^2)\n```\nclass Solution {\n    public int timeRequiredToBuy(int[] tickets, int k){\n        int n= tickets.length;\n        int time=0;\n    \n        if(tickets[k]==1) return k+1;\n        while(tickets[k]>0){\n            for(int i=0;i<n;i++){\n                if(tickets[i]==0) continue;\n                tickets[i]=tickets[i]-1;\n                time++;\n                if(tickets[k]==0) break;\n            }\n        }k--;\n        return time;\n    }\n}\n\n```\n## Optimized approach: without extra space\n\n- Time complexity: O(N)\n- - space complexity: O(1)\n```\nclass Solution {\n    public int timeRequiredToBuy(int[] tickets, int k) {\n        int time = 0;\n        for(int i = 0;i<tickets.length;i++){\n            if(i <= k){\n                time += Math.min(tickets[k],tickets[i]);\n            }else{\n                time+= Math.min(tickets[k] - 1,tickets[i]);\n            }\n        }\n        return time;\n    }\n}\n\n```\n## Queue approach : taking extra space\n- Time complexity: O(N)\n- space complexity: O(N)\n```\nclass Solution {\n    public int timeRequiredToBuy(int[] tickets, int k) {\n        Queue<Integer> q = new LinkedList<>();\n\n        for ( int i = 0; i < tickets.length; i++){\n           q.add(i);\n        }\n        int count = 0;\n        while(!q.isEmpty()){\n            ++count;\n            int front = q.poll();\n            if(tickets[front] >= 1){\n                tickets[front] -= 1;\n            }\n            if(k == front && tickets[front] == 0){\n                break;\n            }\n            if(k != front && tickets[front] == 0){\n                continue;\n            }\n            q.add(front);\n        }\n        return count;\n    }\n}\n```\n![cat-upvote.jpg](https://assets.leetcode.com/users/images/7c799b02-abd9-44f8-98a2-e4830340d206_1692193011.7738297.jpeg)\n
['Array', 'Math', 'Queue', 'Java']