# Questions tagged [complexity]

Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.

391 questions
Filter by
Sorted by
Tagged with
1answer
97 views

### For every integer in an array, find the nearest greater integer both before and after it

The given code gives correct output but exceeds the time limit and I have no idea how to optimize it. I know it is of $O(n^2)$ complexity but I am not able to get anywhere near to optimizing it. ...
1answer
76 views

### Finding time complexity of my solution to the 'longest palindrome' problem in Python

Here is a short version! ...
6answers
2k views

### Award Budget Cuts implementation in Java

PRAMP Award Budget Cuts The awards committee of your alma mater (i.e. your college/university) asked for your assistance with a budget allocation problem they’re facing. Originally, the committee ...
2answers
128 views

### Compare Strings

You have been given two strings, A and B (of length N each) and Q queries. The strings contain only 0s and/or 1s. For every query, you are given an index i. You have to update the value at ...
2answers
4k views

### Program to shorten URL and decode it back to get original URL

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL. Design the encode and ...
1answer
640 views

### Max Increase to Keep City Skyline in Java

In a 2-dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can ...
2answers
568 views

### Pancake sort inteview using java

Given an array of integers arr: Write a function flip(arr, k) that reverses the order of the first k elements in the array <...
1answer
188 views

### Compute the height of a tower made of buckets

I need to speed up my algorithm. It is about finding the height of a tower. The tower is built from buckets. Each bucket has height and radius (1 <= height,radius <= 1000). Variable ...
1answer
75 views

### Algorithmic complexity of this algorithm to find all ordered permutations of length X

I have written a recursive function to generate the list of all ordered permutations of length X for a list of chars. For instance: ['a', 'b', 'c', 'd'] with X=2 will give [['a', 'a'], ['a', 'b'], ['...
0answers
612 views

### Finding the majority element in a sequence of integers in $O(n \log n)$

I wrote this piece of code as solution to a problem set that required finding the majority element in a list using divide and conquer in $O(n \log n)$. The majority element is defined as the ...
2answers
1k views

### Merge non overlapping intervals

Merge Intervals Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their ...
1answer
881 views

### Intersection of two lists in Python

I am currently working on an algorithm, which involves finding the intersection of two lists. That is, given the following inputs [1,2,2,1],...
4answers
1k views

### Reverse the digits of an Integer

Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Return 0 if the result overflows and does not fit in a 32 bit signed integer This is my approach: <...
1answer
492 views

### “Tara's Beautiful Permutations” challenge

I'm practising my coding skills using Python to answer medium to difficult problems on sites like HackerRank. Here is the challenge. Given an array of integers, where each number can appear at most ...
1answer
847 views

### Hackerrank “Breaking the Record” solution

I have solved the hacker rank problem listed here. Given a sequence of scores, I need to count the number of times the records for the high and low scores have been broken. Easiest way for me was to ...
1answer
73 views

### Compute leaderboard of competitive riders throughout a season

I have a table in my DB that contains Riders as rows and their points throughout the season as columns. Here are the columns: ...
4answers
1k views

### Power of two integers

Challenge: Given a positive integer which fits in a $32$ bit signed integer, find if it can be expressed as $A^P$ where $P > 1$ and $A > 0$. A and P both should be integers. ...
1answer
723 views

### Return the optimal time slot

Implement a function meetingPlanner that given the availability, slotsA and slotsB, of two people and a meeting duration dur, returns the earliest time slot that works for both of them and is of ...
3answers
3k views

### Return the anti-diagonals

Give a N*N square matrix, return an array of its anti-diagonals. Look at the example for more details. Example: Input: ...
3answers
222 views

### Finding the number of ways to partition {1,2, …, N} into p1 and p2 such that sum(p1) == sum(p2)

I am trying to write a space and time efficient algorithm to calculate the number of ways to partition a set of integers {1, 2, ..., N} into two partitions such that the sums of integers in the two ...
0answers
42 views

### Method that adds edges to a graph until all nodes have the given degree

Exercise 2-3 in Think Complexity: Complexity Science and Computational Modeling by Allen B. Downey asks us to implement a method for a class of undirected graphs: Write a method named ...
5answers
2k views

### Find The Duplicates in two arrays

Find The Duplicates Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note ...
2answers
467 views

### Space complexity of the “add two binary strings” challenge

I was solving this problem of "adding two string binary numbers" and came up with the following algorithm. I am trying to analyze its time and space complexity. While I was satisfied with its time ...
1answer
127 views

### 2D discrete motion planner

I am writing a 2D discrete motion planner for a task with specific instructions. The instructions for the search algorithm are contained entirely in the docstring for the ...
1answer
84 views

### Leet Code :: Merge Binary Tree :: Time Complexity [closed]

Problem Statement: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into ...
3answers
640 views

### Detecting if two strings are anagrams

I am trying to write a function that detects if two strings are anagrams of one another; more specifically, I want the function to be linear in its time complexity ($O(n)$ where $n$ is the length ...
2answers
717 views

### Bottom-up singly linked list merge sort in C++

This is an implementation of a singly linked list merge sort I did on paper during a job interview recently, using a bottom-up approach. The requirement was simply "implement a merge sort for a ...
1answer
169 views

### Binary search for IOI problem: Cave

Question http://www.ioinformatics.org/locations/ioi13/contest/day2/cave/cave.pdf Code ...
1answer
1k views

### Sort multidimensional array based of the difference in the value

Sort multidimensional array based of the difference in the value, if value is same sort on first column. Constrains: No of rows can be any but fixed no of column ie 2. Example: <...
2answers
127 views

### Finding duplicates in arrays

I'm given two sorted arrays, arr1 and arr2. They can either be of the same length or arr2 ...
1answer
364 views

### Pig Latin Script and Runtime

Wrote a basic pig latin script in python where the input is a string and it outputs the pig latin equivalent. I was just wondering what the runtime of this code would be and if there was a way to make ...
1answer
141 views

### Comparing two n×m matrices

I have to do a pairwise compare of a couple of text files. They have the following format: ...
1answer
936 views

### Genomic Range Query in Python

Recently, I worked on one of the Codility Training - Genomic Range Query (please refer to one of the evaluation report for the detail of the task. The solution in Python is based on prefix sum, and ...
0answers
48 views

### RTB, SSPs is True 2nd Price Auction Program

I've created this program that is intended to check if SSPs in RTB auctions run true second price auction. The program is running properly and returning the values as desired. I would like to get ...
2answers
985 views

### Most popular element with count in Array with Java

Here is the input array of int values Example: { 5, 4, 6, 5, 1, 0, 7, 7, 3, 5 } Find the most repeated element with its count, example output; ...
2answers
107 views

### Adding input strings and finding occurrences of certain prefixes

A user inputs data using a keyword add word and when he wants to find words with particular prefix then he enters find keyword. ...
1answer
341 views

### Find all pairs in an array whose absolute difference equals x

I have an array A of integers with n values and an integer x. I need to find all the pairs in that array whose absolute ...
2answers
337 views

### Design a O(1) data structure

How would I implement a data structure that supports the following in constant time? I got this question at a job interview, and the following is my solution. Please check my approach, or suggest a ...
1answer
572 views

### N queens variation recursion Python 3

I am trying to solve a modified version of the N-queens problem, where the addition is that for any NxN board (3<=N<=12) there are M holes (0<=M<=N^2) that are placed at random (but given) ...
1answer
68 views

### Given an array of integers, find and print its number of negative subarrays on a new line

Given an array of N integers, find and print its number of negative subarrays (i.e sub arrays having negative summation) on a new line. My code is taking $\mathcal{O}(n^2)$ time. How can I improve ...
0answers
2k views

### Find the length of minimum sub array with maximum degree in an array

I tried solving a problem in Hackerrank which is to find the length of minimum sub array with maximum degree in an array. For example, consider the example {2, 2, 1, 2, 3, 1, 1} the min sub-array ...
2answers
527 views

### Adding Combinations of Numbers in an Array

Could someone help me optimize this code for time complexity? What is the best way to do this that doesn't include nested for loops? Take an array of integers and return a list of sums of every ...
2answers
2k views

### Python PEMDAS calculator [closed]

The goal of this calculator is to evaluate an expression with PEMDAS in mind (no parenthesis yet, adding soon). Although the program works, I want to make it as efficient as possible with the approach ...
4answers
2k views

### Maximum consecutive subarray sum for a variable sliding window size

The Problem: Given an array of integers L find the largest sum of a consecutive subarray of size k or less. Constraints: ...
1answer
216 views

### Category of sorting algorithm and complexity [closed]

Just for fun, I wrote a sorting algorithm. I did not compare this with existing sorting algorithms.Can someone tell me what class of sorting algorithm this is and it's complexity? The algorithm ...
1answer
2k views

### Counting the number of ways to break an amount into coins

I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations: quarter: 25 cents dime: 10 cents nickel: 5 cents pennies: 1 cent There are ...
1answer
3k views

### Calculating the most profit from an array of stock prices

I'm a newbie learning how to code, and I am trying to find the most efficient way to calculate the most profit from an array of stock prices. For a given array,I have a list of stock prices over n ...
1answer
2k views

### Implementation of Prim's Algorithm to find minimum spanning tree

What is the time complexity of the following code? I'm implementing Prim's Algorithm with adjacency matrix representation of the graph and priority queue. ...
3answers
1k views

### Given some integers, return the k most frequent elements

Given a non-empty array of integers, return the k most frequent elements. For example, given [1,1,1,2,2,3] and k = 2, return <...
1answer
90 views

### Two approaches to count occurrences of one char in a String in Java

I have two approaches: First Approach: ...